</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Greedy and Structure

What is this?

Both problems have short answers that are worthless without the argument behind them. Patch Array adds numbers so every sum up to n is reachable, and the rule (always add the smallest currently unreachable value) doubles the reachable range each time. Task Scheduler has a closed-form formula whose derivation is the interview, and the code is short.

Greedy and Structure: Patch Array decision and Task Scheduler formula

Fun fact: Task Scheduler needs no scheduling. Take the most frequent task, occurring mx times: it forces mx − 1 gaps of width n + 1, and then the tasks tied at that frequency finish the last block, which gives (mx − 1) × (n + 1) + k. Every other task fits into the idle slots, and if there are too many to fit, they simply fill every idle slot and the answer becomes len(tasks). So the answer is max(len(tasks), (mx − 1) × (n + 1) + k). One line, no simulation. The argument that the busiest task alone determines the shape is what is actually being asked for.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


Core idea: find the quantity that constrains everything else (the smallest unreachable sum, the most frequent task) and the greedy follows from it, along with the proof you will be asked for.


1. The reachable range doubles

miss, i, patches = 1, 0, 0                       # everything in [1, miss) is reachable
while miss <= n:
    if i < len(nums) and nums[i] <= miss:
        miss += nums[i]; i += 1                  # extend using what we already have
    else:
        miss += miss; patches += 1               # patch with `miss` itself → range doubles
return patches

The invariant is the whole solution: every sum in [1, miss) is reachable. If the next available number is at most miss, adding it extends the range to miss + nums[i] with no gap. If it is larger, miss itself is unreachable and must be patched. Patching with exactly miss extends the range to 2 × miss, the largest extension any single number could give.

That doubling is also the complexity argument: the range at least doubles per patch, so at most O(log n) patches are ever needed.

2. The busiest task sets the length

c = Counter(tasks)
mx = max(c.values())                             # the most frequent task's count
k = sum(1 for v in c.values() if v == mx)        # how many tasks tie at that count
return max(len(tasks), (mx - 1) * (n + 1) + k)

The max against len(tasks) is the case people miss. When there are many distinct tasks, the idle slots fill up completely and no idling is required at all, so the formula would then understate the answer, and the total task count is the true answer.

k matters because every task tied at the maximum frequency must appear in the final block, extending it by one each.


3. A 30-second worked example (patching)

nums = [1, 5, 10], n = 20

Patch Array worked example: two patches to reach 20

The trace is miss = 1 → 2 (take the 1), patch 2 (miss = 4), patch 4 (miss = 8), take 5 (13), take 10 (23). The two patches double the range each time (2 to 4, then 4 to 8) while the numbers already present extend it by their own value. After the second patch the array's own 5 and 10 are usable, and they carry the range past 20 on their own. Patching with anything smaller than miss would have left miss still unreachable; anything larger would have left a gap.


4. Where you'll actually meet this

  • Coin design. "Which extra coin values let a tray of coins pay every price up to n" is Patch Array, where each coin is used at most once.
  • Cooldown scheduling. Task Scheduler's formula is a lower bound for any job runner that must space out repeats of the same job.
  • Rate-limited dispatch. The most frequent recipient sets a floor on the total time when the same recipient cannot be hit twice within a window.

5. Problems in this chapter

Patch Array

Fewest additions so every sum in [1, n] is reachable. Track the smallest unreachable sum; use the next number when it fits, patch with miss otherwise. The lesson starts from a reachability-table brute force, O(n * (len + log n)) time and O(n) space.
Pattern: greedy with a doubling invariant. Target: O(len(nums) + log n) time, O(1) space.

Task Scheduler

Least time to run all tasks with a cooldown n between identical ones. The lesson starts from a max-heap simulation and then derives the closed form from the most frequent task's count and the number of tasks tied with it.
Pattern: closed-form from the binding constraint. Target: O(len(tasks)) time, O(1) space (the alphabet is at most 26 letters).


6. Common pitfalls

  • Patching with a number other than miss. Smaller leaves the gap; larger wastes the extension.
  • Losing the invariant. State "everything in [1, miss) is reachable" out loud and every step follows.
  • Overflow on miss += miss in fixed-width languages when n is near the integer limit.
  • Forgetting max(len(tasks), …) in the scheduler, which understates the answer when idle slots fill.
  • Omitting k, the number of tasks tied at the maximum frequency, which extends the final block.
  • Simulating the scheduler. It works, but it ticks the clock once per time unit, including every idle one, and the formula is what is being asked for.
  • Stating a greedy without its argument. Both of these are judged on the proof.

7. Key takeaways

  1. Find the binding constraint (the smallest unreachable sum, the busiest task) and the greedy follows.
  2. An invariant makes a greedy provable. [1, miss) is the whole argument for Patch Array.
  3. Doubling gives the complexity for free: at most O(log n) patches.
  4. Patch with exactly the gap. It is the unique choice that neither wastes nor falls short.
  5. A closed form can replace a simulation, and knowing why is the point.
  6. Guard the formula with a lower bound. len(tasks) is a regime, not an edge case.
  7. Why interviewers like it: both answers are short, so all the signal is in the explanation.

Order: Patch Array → Task Scheduler.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.