In a greedy-stays-ahead proof for covering houses on a line with fewest towers, what is the induction hypothesis?

middleshould knowfreq 42%

answer

you never modify the other solution here
invent a number that measures progress
how far right does k towers reach?
greedy is never behind at any step k
so it finishes by the step the optimum finishes

basics

~20 s

The hypothesis is that after k towers, the greedy has covered at least as long a prefix of the houses as any other solution's leftmost k towers. Never being behind means greedy never needs more towers than an optimal solution.

solid answer

~50 s

Stays-ahead inducts on the step count with an explicit progress measure. Here the measure is how far along the sorted houses the first k towers reach: let g(k) be the last house covered by greedy's first k towers, and s(k) the same for any other solution's k leftmost towers. The claim is g(k) >= s(k) for every k. Base case: any solution must cover the leftmost house, and greedy places its first tower at the rightmost position that still covers it, so no one reaches further with one tower. Inductive step: greedy starts from a position no worse than the other solution's and again pushes its next tower as far right as legality allows. Conclusion: if some solution finishes in m towers, greedy has covered everything by m too, so greedy uses at most m.

Stays-ahead inducts on the step count with an explicit progress measure. Here the measure is how far along the sorted houses the first `k` towers reach: let `g(k)` be the last house covered by greedy's first `k` towers, and `s(k)` the same for any other solution's `k` leftmost towers. The claim is `g(k) >= s(k)` for every `k`. Base case: any solution must cover the leftmost house, and greedy places its first tower at the rightmost position that still covers it, so no one reaches further with one tower. Inductive step: greedy starts from a position no worse than the other solution's and again pushes its next tower as far right as legality allows. Conclusion: if some solution finishes in `m` towers, greedy has covered everything by `m` too, so greedy uses at most `m`.

code

pseudocode · 9 lines

pseudocode

// house[0..n-1] sorted ascending; a tower at p covers [p-r, p+r]
i = 0
towers = 0
while i < n:
    p = house[i] + r           // rightmost spot still covering house[i]
    towers = towers + 1
    while i < n and house[i] <= p + r:
        i = i + 1              // skip every house this tower serves
return towers

go deeper

for a junior

Recall the two ingredients: a number that measures progress after k steps, and the claim that greedy's number is never smaller than anyone else's. Practise saying what the number is before saying why greedy wins.

for a middle

Walk the base case and the inductive step explicitly, and justify why placing at the far edge of the range is what keeps greedy ahead. Then close the loop: never behind at step m means never more than m steps.

for a senior

Show you check the measure before trusting it. Name a measure that would make the induction valid but useless, and explain why the covered-prefix length is the one that controls the tower count.

for a principal

Decide when this level of rigour is worth buying. Argue for which greedy rules in a codebase get a written proof, which get a documented approximation bound, and how the choice tracks the cost of being wrong.

The setting

Houses sit at known coordinates along a straight road. A tower placed at coordinate p serves every house in [p - r, p + r]. You want the fewest towers that leave no house unserved. The greedy rule is: walk the houses left to right; when you meet the first uncovered house h, place a tower at h + r — the furthest-right position that still reaches h — then skip every house it now covers, and repeat.

That rule is easy to state and easy to doubt. Pushing the tower as far right as possible feels like it might strand h itself, or overshoot into a gap. The proof has to convert the intuition ("reaching further can never hurt") into something an interviewer accepts.

Two proof shapes, and why this one fits

An exchange argument transforms an arbitrary optimal solution into greedy's, one swap at a time. A stays-ahead argument never touches the other solution at all. Instead it invents a numeric measure of progress, and shows greedy dominates on that measure at every step. Stays-ahead is usually the easier shape when the objective is "fewest steps" or "most items", because dominating a per-step measure translates directly into a bound on the step count.

Choosing the measure — the step everyone skips

The measure has to satisfy one requirement, and stating it is what separates a real proof from a hand-wave:

Being ahead on the measure must imply doing at least as well on the actual objective.

Here, sort the houses ascending and let the measure after k towers be the length of the prefix of houses that those k towers cover. Greedy always covers a prefix by construction. For any other solution, order its towers left to right and ask the same question of its first k. Domination on this measure controls the objective directly: whoever covers the whole list first used fewer towers.

A plausible-looking measure that fails the requirement: "average distance from a house to its nearest tower". You can be ahead on that and still need more towers, so no induction on it proves anything about the count.

Base case

With one tower: every solution must serve the leftmost house h0, so every solution's leftmost tower sits at some p <= h0 + r, and its coverage ends at p + r <= h0 + 2r. Greedy chooses p = h0 + r exactly, so its coverage ends at h0 + 2r, the maximum possible. No solution covers a longer prefix with one tower.

Inductive step

Assume greedy's first k towers cover a prefix at least as long as any other solution's first k. Consider tower k+1. Greedy resumes at the first house it has not covered, which is at or beyond the first house the other solution has not covered. Greedy then places at that house plus r, again the furthest-right legal position, so its coverage after k+1 towers ends at least as far right as the other solution's. The hypothesis holds at k+1.

Two details carry the step: greedy's starting point is no worse (from the hypothesis), and greedy's local choice maximises the new right edge (the safe-move flavour of the rule). Drop either and the induction collapses.

Conclusion

Suppose some optimal solution uses m towers and covers every house. By the hypothesis at k = m, greedy's first m towers cover a prefix at least as long — that is, all of it. Greedy therefore halts having placed at most m towers, so greedy is optimal. Note what the argument never claims: greedy's tower positions are not claimed to match the optimal solution's. Only the count is.

Where candidates lose the point

Comparing against "the" optimal solution. The hypothesis must hold against any solution, otherwise the final step ("take an optimal one and compare at step m") is unavailable.
Forgetting to order the other solution's steps. Greedy produces towers left to right; the other solution's towers must be sorted the same way before "its first k" means anything.
Asserting domination instead of proving it. "Greedy is obviously ahead" is where the interview stalls; the inductive step is one sentence about the resume point and one about the placement rule.
Choosing a measure that does not control the objective. This is the silent failure: the induction can be perfectly valid and prove nothing you wanted.
Claiming the measure must strictly increase. It only has to dominate; ties are fine and common.

## The setting Houses sit at known coordinates along a straight road. A tower placed at coordinate `p` serves every house in `[p - r, p + r]`. You want the fewest towers that leave no house unserved. The greedy rule is: walk the houses left to right; when you meet the first uncovered house `h`, place a tower at `h + r` — the furthest-right position that still reaches `h` — then skip every house it now covers, and repeat. That rule is easy to state and easy to doubt. Pushing the tower as far right as possible feels like it might strand `h` itself, or overshoot into a gap. The proof has to convert the intuition ("reaching further can never hurt") into something an interviewer accepts. ## Two proof shapes, and why this one fits An exchange argument transforms an arbitrary optimal solution into greedy's, one swap at a time. A **stays-ahead** argument never touches the other solution at all. Instead it invents a numeric measure of progress, and shows greedy dominates on that measure at every step. Stays-ahead is usually the easier shape when the objective is "fewest steps" or "most items", because dominating a per-step measure translates directly into a bound on the step count. ## Choosing the measure — the step everyone skips The measure has to satisfy one requirement, and stating it is what separates a real proof from a hand-wave: > Being ahead on the measure must imply doing at least as well on the actual objective. Here, sort the houses ascending and let the measure after `k` towers be **the length of the prefix of houses that those `k` towers cover**. Greedy always covers a prefix by construction. For any other solution, order its towers left to right and ask the same question of its first `k`. Domination on this measure controls the objective directly: whoever covers the whole list first used fewer towers. A plausible-looking measure that fails the requirement: "average distance from a house to its nearest tower". You can be ahead on that and still need more towers, so no induction on it proves anything about the count. ## Base case With one tower: every solution must serve the leftmost house `h0`, so every solution's leftmost tower sits at some `p <= h0 + r`, and its coverage ends at `p + r <= h0 + 2r`. Greedy chooses `p = h0 + r` exactly, so its coverage ends at `h0 + 2r`, the maximum possible. No solution covers a longer prefix with one tower. ## Inductive step Assume greedy's first `k` towers cover a prefix at least as long as any other solution's first `k`. Consider tower `k+1`. Greedy resumes at the first house it has not covered, which is at or beyond the first house the other solution has not covered. Greedy then places at that house plus `r`, again the furthest-right legal position, so its coverage after `k+1` towers ends at least as far right as the other solution's. The hypothesis holds at `k+1`. Two details carry the step: greedy's starting point is no worse (from the hypothesis), and greedy's local choice maximises the new right edge (the safe-move flavour of the rule). Drop either and the induction collapses. ## Conclusion Suppose some optimal solution uses `m` towers and covers every house. By the hypothesis at `k = m`, greedy's first `m` towers cover a prefix at least as long — that is, all of it. Greedy therefore halts having placed at most `m` towers, so greedy is optimal. Note what the argument never claims: greedy's tower *positions* are not claimed to match the optimal solution's. Only the count is. ## Where candidates lose the point - **Comparing against "the" optimal solution.** The hypothesis must hold against *any* solution, otherwise the final step ("take an optimal one and compare at step `m`") is unavailable. - **Forgetting to order the other solution's steps.** Greedy produces towers left to right; the other solution's towers must be sorted the same way before "its first `k`" means anything. - **Asserting domination instead of proving it.** "Greedy is obviously ahead" is where the interview stalls; the inductive step is one sentence about the resume point and one about the placement rule. - **Choosing a measure that does not control the objective.** This is the silent failure: the induction can be perfectly valid and prove nothing you wanted. - **Claiming the measure must strictly increase.** It only has to dominate; ties are fine and common.

How does a stays-ahead proof differ from an exchange argument?
An exchange argument edits an optimal solution, swapping greedy's choices in one at a time until it becomes greedy's output. Stays-ahead never touches the other solution: it defines a numeric progress measure and shows greedy dominates it at every step. Stays-ahead tends to be easier when the objective is a count of steps; exchange tends to be easier when the objective is a sum or a value.
What must you verify about the progress measure before the induction is valid?
That dominating the measure implies dominating the objective. A measure can be perfectly well defined, and the induction perfectly valid, while proving nothing you care about — average distance to the nearest tower is such a measure here. Check the implication first, then do the induction.
Why does the greedy place the tower at the house's coordinate plus r rather than on the house itself?
Placing it on the house wastes half the range to the left, where nothing is left uncovered. The rightmost legal position maximises the new right edge, which is exactly the quantity the induction tracks. That local maximisation is what lets the inductive step close in one line.

saying these in an interview costs you the question

Compares greedy only against one specific optimal solution
Picks a progress measure that does not control the objective
Asserts greedy is ahead without an inductive step
Forgets to order the other solution's steps left to right
Claims greedy's placements must match the optimal placements
Insists the measure strictly increases rather than dominates

In a greedy-stays-ahead proof for covering houses on a line with fewest towers, what is the induction hypothesis?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The setting

Two proof shapes, and why this one fits

Choosing the measure — the step everyone skips

Base case

Inductive step

Conclusion

Where candidates lose the point

▾common follow-ups3 questions

▾red flags6 flags

§ context

▾related questions7 questions

▾related topics4 topics

The setting

Two proof shapes, and why this one fits

Choosing the measure — the step everyone skips

Base case

Inductive step

Conclusion

Where candidates lose the point

answer

go deeper

context