Editor

The Most Varied Stretch

#633 · Sliding window · Advanced · Fast enough · 115 XP · about 20 min

An ice cream shop features one flavor each day, and flavors lists the flavor codes in order: flavors[0] was featured on day 0. For an ad the shop wants the run of k days in a row that featured the most different flavors.

Write most_varied(flavors, k) that returns a tuple (count, start): the largest number of different flavors in any k consecutive days, and the first day of the earliest run that has that many.

Examples

most_varied([1, 2, 1, 3, 4, 4, 2], 3)  # returns (3, 1)
most_varied([5, 5, 5], 2)              # returns (1, 0)
most_varied([7, 8, 9], 3)              # returns (3, 0)

In the first example the three-day runs hold 2, 3, 3, 2 and 2 different flavors. Days 1 to 3 and days 2 to 4 both have 3, and the earlier run starts on day 1.

Constraints

  • 1 <= k <= len(flavors) <= 200,000
  • Flavor codes are whole numbers from 0 to 1,000,000.

Time limit

Each test must finish within 10 seconds, and the hidden tests have 200,000 days with runs tens of thousands of days long.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.