Preview Download Budget

Earliest start index of k consecutive array elements with minimum sum

EasySliding WindowArraysRunning Sum

A music streaming app wants to download a preview consisting of exactly k consecutive tracks from an ordered playlist.

The array download_kb gives the additional download size, in kilobytes, for each track. A value of 0 means that track is already cached. Tracks must stay in their original order, and the preview cannot wrap around the end of the playlist.

Return the zero-based starting index of the preview requiring the fewest total kilobytes. If several previews have the same minimum total, return the smallest starting index.

Examples

Example 1

Input: download_kb = [8,4,3,5,2], k = 2
Output: 1

For previews of two tracks, the adjacent pairs require 12, 7, 8, and 7 kilobytes. Two pairs share the minimum, so choose the earlier one.

Example 2

Input: download_kb = [6,0,0,0,9], k = 3
Output: 1

Three consecutive tracks are already cached together, so that preview requires no additional download.

Example 3

Input: download_kb = [5,2,7], k = 3
Output: 0

The preview must contain the entire playlist, leaving only one possible starting position.

Constraints

  • 1 <= download_kb.length <= 10,000
  • 0 <= download_kb[i] <= 1,000,000
  • 1 <= k <= download_kb.length

The intended solution takes O(n) time and O(1) auxiliary space, where n is the playlist length. Download totals can exceed the range of a signed 32-bit integer, but remain exactly representable by JavaScript Number.

Hints

Show hint 1

First calculate the download total for the preview starting at index 0.

Show hint 2

When a preview moves one position to the right, one track leaves and one enters. Update the best starting index only when the total becomes strictly smaller.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you also return the minimum number of kilobytes without changing the time complexity?
  • How would you process tracks arriving as a stream if you only needed to report the best preview after the stream ended?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem