Minimum covering window

In this lesson you learn to find the shortest stretch that contains every required value, each as many times as required. You keep the counts map and the need map from earlier lessons, add one counter, and let the window grow and shrink.

A music streaming app sells sponsored blocks on its radio channels. A block is a stretch of consecutive plays in a channel's schedule. Your team lead brings the sponsors' requirement.

Your team lead says: Each sponsor names tracks that must play inside its block, and some must play twice. Sponsors pay by length, so find the shortest block.

If two blocks are equally short, take the earlier one. If no block works, say so.

The planner checks every campaign against every channel each night, and it must finish within one hour.

Here is one short test schedule of track ids: [2, 3, 2, 5, 5, 2, 8, 7, 5, 1]. The campaign needs track 5, the sponsor's jingle, twice. It also needs tracks 7 and 2 once each, so the required list is [5, 7, 5, 2].

Order does not matter, but repeats do. A block may also hold other tracks.

Before you write code, solve the test schedule by hand. It takes three minutes, and it shows you where the work goes.

You work through it on the whiteboard. You write one row for each start. From each start, you extend the block until it holds two 5s, one 7 and one 2.

The first attempt#

You turn the hand method into code.

Start with a correct version. From every start, extend the block until its counts cover the campaign.

def covers(counts, need):
    for track, copies in need.items():  # every required track needs enough copies
        if counts.get(track, 0) < copies:
            return False
    return True


def shortest_block(schedule, required):
    need = {}
    for track in required:
        need[track] = need.get(track, 0) + 1
    best = [-1, -1]
    for start in range(len(schedule)):
        counts = {}
        for end in range(start, len(schedule)):  # extend this block one play at a time
            counts[schedule[end]] = counts.get(schedule[end], 0) + 1
            if covers(counts, need):
                if best[0] == -1 or end - start < best[1] - best[0]:
                    best = [start, end]
                break
    return best

This is correct, and it keeps the earlier block on a tie. For the test schedule it reads 46 plays, which takes no time at all. The team keeps it as the reference: every faster version must give the same answers.

How much work is it in general? The worst case is a channel that never plays one of the sponsored tracks. Then no block covers, and every start reads to the end. With n plays, that is n + (n − 1) + ... + 1 = n(n + 1) ÷ 2 reads, and a map check after each one.

The scale check#

Now check the real planner.

Each night the planner checks 50 campaigns against the next 7 days of all 10,000 channels. Most channels never play a campaign's tracks.

Here is the count for one night:

• A track lasts about 3 minutes, so 7 days hold 7 × 24 × 60 ÷ 3 = 3,360 plays per channel.
• On a channel that never plays one of the campaign's tracks, every start reads to the end: 3,360 × 3,361 ÷ 2 = 5,646,480 reads.
• Across 10,000 channels and 50 campaigns: about 2.82 × 10^12 reads, before any map checks.

The first attempt is correct, but at this size it misses the deadline by hours. Now the team looks for the work it repeats.

Can we do better?#

Look at row 0 of the hand trace.

Block 0 to 7 already covers. Why throw it away and read plays 1 to 7 again for start 1? Can we do better?

The block from start 1 needs only plays that block 0 to 7 already holds. So keep one window and never read a play twice.

Two facts make this safe. Adding plays to a block never removes a track, so a covering block stays covering when it grows. Removing plays can only lose tracks, so a block that does not cover still fails when it shrinks.

So the window has two moves. Grow right until it covers. Then shrink from the left while it still covers, and record each covering window on the way.

A window that holds every required value, each as many times as required, is a covering window. The shortest one is the minimum covering window.

The missing counter#

To know whether the window covers, the first attempt checks the whole need map after every play. You can keep one number instead.

You need three things. The need map counts the required list: here 5 is needed twice, and 7 and 2 once. The counts map counts the window, as in Windows with counts.

The third is missing, the number of required copies the window still lacks. This number is the missing counter, and it starts at the length of the required list, 4.

You never recompute it. It changes only at the edge of a need:

• A value joins and its count rises to at or below its need: it fills a gap, so missing goes down by 1.
• A value joins and its count rises above its need: it is a surplus copy, so missing stays the same.
• A value leaves and its count falls below its need: it opens a gap, so missing goes up by 1.
• Any other change, and any value that is not required, leaves missing as it is.

The window covers exactly when missing is 0. Compare the matched counter from Windows with counts. It counted values at exactly their need, because a reordering allows no extras. A cover allows extras, so here you count the copies that are still absent.

The test schedule, one window#

Watch missing on the test schedule. Track 2 joins at index 0, and missing drops from 4 to 3. Track 2 joins again at index 2, but its need is 1, so this surplus copy changes nothing.

The two 5s bring missing to 1. Track 7 joins at index 7, and missing reaches 0: block 0 to 7 covers.

Now the shrink. Record 0 to 7, and index 0 leaves. It is track 2, but another 2 is still inside, so missing stays 0.

Record 1 to 7, and track 3 leaves. Record 2 to 7, and the second 2 leaves; one 2 is still inside.

Record 3 to 7, length 5, and track 5 leaves. Now only one 5 is inside, below its need of 2, so missing rises to 1 and the shrink stops at left = 4.

When the 5 at index 8 joins, block 4 to 8 covers in 5 plays too. It is not shorter, so the best stays 3 to 7.

Where the record goes#

In the longest window of At most K, you recorded after the shrink, when the window was valid again. Here it is the other way round. After the shrink loop, missing is 1, so the window no longer covers.

The window is valid only inside the loop. So record first, then let the value at left leave. This is the same rule as the shortest window in the first lesson of this module.

Why is this fast? Each value joins once, when right reaches it, and leaves at most once, when left passes it. Building the need map reads the m required values once. So the pass is O(n + m), and the loop inside a loop does not make it O(n^2).

The race counts the plays each version reads on seeded random schedules. Track 7 plays about once in 100 plays. At 100,000 plays, the first attempt reads 13,548,824 plays. The covering window makes 199,924 count updates: one per join and one per leave.

Here is the rule that keeps this correct. Every line of the template below exists to protect it.

Why can left never move back? Say the window from left to right covers. Every later window with the same left is longer, so it can never beat the one you have recorded. Once you record it, the value at left may leave for good.

If the window does not cover, no shorter window that ends at right covers either. So the only useful move is to grow.

Why does the earliest window win a tie? Windows are recorded in order of their right edge. Two windows of the same length that end in order also start in order. So the template replaces the best only when a window is strictly shorter.

The template: the shortest covering window#

The template returns [start, end] of the earliest shortest window that covers required, or [-1, -1] if no window does.

def min_cover(values, required):
    # [1] Count what is required; the empty window lacks every copy.
    need = {}
    for value in required:
        need[value] = need.get(value, 0) + 1
    missing = len(required)
    window = {}
    left = 0
    best_start = -1
    best_end = -1
    for right in range(len(values)):
        # [2] The value at right joins; missing drops only while its count is at or below its need.
        joining = values[right]
        window[joining] = window.get(joining, 0) + 1
        if window[joining] <= need.get(joining, 0):
            missing -= 1  # it fills a gap; a surplus copy fills none
        # [3] While the window covers, record it if shorter, then the value at left leaves.
        while missing == 0:
            if best_start == -1 or right - left < best_end - best_start:
                best_start = left  # strictly shorter only, so the earliest of equal windows stays
                best_end = right
            leaving = values[left]
            window[leaving] -= 1
            if window[leaving] < need.get(leaving, 0):
                missing += 1  # the window now lacks a copy it needs
            left += 1
    # [4] Report the shortest covering window, or [-1, -1] if none covers.
    return [best_start, best_end]

public int[] minCover(int[] values, int[] required) {
    // [1] Count what is required; the empty window lacks every copy.
    Map<Integer, Integer> need = new HashMap<>();
    for (int value : required) {
        need.put(value, need.getOrDefault(value, 0) + 1);
    }
    int missing = required.length;
    Map<Integer, Integer> window = new HashMap<>();
    int left = 0;
    int bestStart = -1;
    int bestEnd = -1;
    for (int right = 0; right < values.length; right++) {
        // [2] The value at right joins; missing drops only while its count is at or below its need.
        int joining = values[right];
        int count = window.getOrDefault(joining, 0) + 1;
        window.put(joining, count);
        if (count <= need.getOrDefault(joining, 0)) {
            missing--;  // it fills a gap; a surplus copy fills none
        }
        // [3] While the window covers, record it if shorter, then the value at left leaves.
        while (missing == 0) {
            if (bestStart == -1 || right - left < bestEnd - bestStart) {
                bestStart = left;  // strictly shorter only, so the earliest of equal windows stays
                bestEnd = right;
            }
            int leaving = values[left];
            int remaining = window.get(leaving) - 1;
            window.put(leaving, remaining);
            if (remaining < need.getOrDefault(leaving, 0)) {
                missing++;  // the window now lacks a copy it needs
            }
            left++;
        }
    }
    // [4] Report the shortest covering window, or [-1, -1] if none covers.
    return new int[] {bestStart, bestEnd};
}

vector<int> minCover(const vector<int>& values, const vector<int>& required) {
    // [1] Count what is required; the empty window lacks every copy.
    unordered_map<int, int> need;
    for (int value : required) {
        need[value]++;
    }
    int missing = required.size();
    unordered_map<int, int> window;
    int left = 0;
    int bestStart = -1;
    int bestEnd = -1;
    for (int right = 0; right < (int) values.size(); right++) {
        // [2] The value at right joins; missing drops only while its count is at or below its need.
        int joining = values[right];
        int count = ++window[joining];
        auto found = need.find(joining);
        if (found != need.end() && count <= found->second) {
            missing--;  // it fills a gap; a surplus copy fills none
        }
        // [3] While the window covers, record it if shorter, then the value at left leaves.
        while (missing == 0) {
            if (bestStart == -1 || right - left < bestEnd - bestStart) {
                bestStart = left;  // strictly shorter only, so the earliest of equal windows stays
                bestEnd = right;
            }
            int leaving = values[left];
            int remaining = --window[leaving];
            auto needed = need.find(leaving);
            if (needed != need.end() && remaining < needed->second) {
                missing++;  // the window now lacks a copy it needs
            }
            left++;
        }
    }
    // [4] Report the shortest covering window, or [-1, -1] if none covers.
    return {bestStart, bestEnd};
}

function minCover(values, required) {
  // [1] Count what is required; the empty window lacks every copy.
  const need = new Map();
  for (const value of required) {
    need.set(value, (need.get(value) || 0) + 1);
  }
  let missing = required.length;
  const window = new Map();
  let left = 0;
  let bestStart = -1;
  let bestEnd = -1;
  for (let right = 0; right < values.length; right++) {
    // [2] The value at right joins; missing drops only while its count is at or below its need.
    const joining = values[right];
    const count = (window.get(joining) || 0) + 1;
    window.set(joining, count);
    if (count <= (need.get(joining) || 0)) {
      missing--;  // it fills a gap; a surplus copy fills none
    }
    // [3] While the window covers, record it if shorter, then the value at left leaves.
    while (missing === 0) {
      if (bestStart === -1 || right - left < bestEnd - bestStart) {
        bestStart = left;  // strictly shorter only, so the earliest of equal windows stays
        bestEnd = right;
      }
      const leaving = values[left];
      const remaining = window.get(leaving) - 1;
      window.set(leaving, remaining);
      if (remaining < (need.get(leaving) || 0)) {
        missing++;  // the window now lacks a copy it needs
      }
      left++;
    }
  }
  // [4] Report the shortest covering window, or [-1, -1] if none covers.
  return [bestStart, bestEnd];
}

Two details are worth a second look. Step [2] compares the new count with the need, so a surplus copy and a value that is not required both fail the test and leave missing alone. Step [3] checks the need after lowering the count, so it fires only on the copy that opens a gap.

To return only the length, keep the same loop and return best_end - best_start + 1, or 0 when nothing covers. To cover every distinct value of the input, build the need map from the distinct values, each needed once.

Complexity in plain words#

• Time. Building the need map reads the m required values once. Then each of the n values joins once and leaves at most once, and each is one hash map update plus a comparison. That is O(n + m) in all.
• Space. The need map holds one key per distinct required value. The window map in the template holds every distinct value in the window. To keep it at O(m), count only the values that are in the need map.
• No map checks. The missing counter replaces the check of the whole need map after every step. Each join and each leave changes it by at most 1, in O(1) time.
• At planner size. Each channel and campaign needs at most 3,360 joins, 3,360 leaves and 4 need updates: 6,724 in all. Across 10,000 channels and 50 campaigns that is about 3.36 × 10^9 updates: about 34 seconds on one core, instead of 7.8 hours.

Edge cases#

Real production data brings edge cases.

The mistake museum#

if joining in need:
    missing -= 1  # bug: a surplus copy fills no gap

shrank = False
while missing == 0:
    ...  # the value at left leaves, as in the template
    shrank = True
if shrank and (best_start == -1 or right - left < best_end - best_start):
    best_start, best_end = left, right  # bug: the window has just lost a required copy

if missing == 0:  # bug: this must be a while loop
    ...  # record, then the value at left leaves

while all(window.get(value, 0) >= copies for value, copies in need.items()):
    ...  # record, then the value at left leaves

When the pattern does not apply#

Product variations#

Your team lead brings five product changes. Each one keeps a need map, a counts map and a window that grows and shrinks.

Why this matters in real systems#

Explain it back#

In two or three sentences, explain to a teammate how you find the shortest window that covers a required list in one pass. Say when the missing counter changes and where you record the answer. The AI tutor checks your answer against the invariant and the key points of this lesson.

Here is how you could explain it in an interview, now that you have built it.

I keep a need map, a counts map and missing. missing drops only when a count rises to at or below its need.

I grow right until missing is 0. Then, while it stays 0, I record the window and let the value at left leave.

Each value joins once and leaves once, so it is O(n + m). Strictly shorter wins, so ties keep the earliest.

The 60-second interview answer#

Checkpoint#

Ten questions on this lesson. Pass with 80% or more to open the gate to the next stretch on the Academy map.

Practice ladder#

Review cards#

Five cards from this lesson join your spaced-review deck. The first one comes back tomorrow.

This lesson completes the four patterns of Window Tower: fixed and variable windows, windows with counts, at most K, and the minimum covering window.