Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Greedily jump 2 whenever the cloud two ahead is safe (c[i+2] == 0), otherwise jump 1. Each jump counts as one move; the safe-2-first greedy is provably optimal because you can never lose by skipping a cloud you don't have to land on. O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise the greedy choice (always jump 2 over a safe landing) is optimal, and whether you handle the 'fly over a thundercloud' nuance — a 2-jump only cares about the landing cloud, not the one skipped.
Where candidates slip
Checking c[i+1] before allowing a 2-jump (you don't land there, so it's irrelevant), or looping while i < n and overshooting past the last cloud.
How to stand out
State the greedy rule, justify why jumping 2 can never be worse, and mention the equivalent O(n) DP (minJumps[i] = 1 + min(reachable)) as the safety net when greedy correctness is unclear.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAt cloud ii + 2 in range AND c[i+2] == 0?YesNoExplore the full treeCollapse the tree
How to read it:At each cloud, prefer the 2-jump when the landing cloud two ahead is safe.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Greedy — Jump 2 When Safe (Optimal)
1Hint 1Explore hintHide hint
Both a 1-jump and a 2-jump cost the same single move. If a longer jump is legal, can taking it ever hurt you?
2Hint 2Explore hintHide hint
From cloud i, prefer to land on i+2 whenever c[i+2] is safe (0); the cloud at i+1 doesn't matter because you fly over it.
3Hint 3Explore hintHide hint
Walk an index forward: if i+2 is in range and safe, advance by 2, else advance by 1; increment a jump counter each time. Stop at the last index.
A · Core idea
Model the position as a single index i starting at 0 and a jumps counter at 0. Each iteration, look two ahead: if i + 2 is within bounds and c[i + 2] == 0, jump there; otherwise step to i + 1. Count the jump and repeat until i reaches the last cloud.
Why greedy is correct here. This is the crux the interviewer wants you to defend. Every jump — whether of size 1 or 2 — costs exactly one move. So to minimise the number of moves you want each move to cover as much ground as legally possible. A 2-jump lands strictly further than a 1-jump and never blocks a future move: from any safe cloud you can always still take a 1-jump, so reaching cloud i + 2 keeps every option open that cloud i + 1 would have, and then some. Therefore preferring the 2-jump can never increase the total count — the greedy choice is exchange-argument optimal.
Why the intermediate cloud is irrelevant. A 2-jump from i lands on i + 2; you never set foot on i + 1. So c[i + 1] — thundercloud or not — places no constraint on the 2-jump. Beginners add a spurious c[i+1] == 0 check and miss that flying over a thundercloud is exactly what the rules permit.
Why the loop stops at `n − 1`. The goal is the last index, not past it. The condition while i < n − 1 halts the instant we land on the final cloud. Using i < n would let the index walk off the end and over-count. Because the constraints forbid two adjacent thunderclouds and guarantee c[0] = c[n−1] = 0, the greedy walk can always make legal progress and will always terminate exactly on the last cloud.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
c = [0, 0, 1, 0, 0, 1, 0]Array state
i=0
c[2]=1 → jump 1 to i=1
4C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
When all moves cost the same and a bigger move never removes a future option, 'take the biggest legal step' is provably optimal — no DP table needed. The exchange argument (a longer jump dominates a shorter one) is the one-sentence proof to say out loud.
ComplexityO(n) time, O(1) space — The index only moves forward and advances by at least 1 each iteration, so the loop runs at most n times → O(n). A handful of scalar variables → O(1) space.
E · Edge cases and pitfalls6c = [0, 0] — i=0, i+2=2 out of range → jump 1 to i=1 = n-1. Returns 1.Explore edge casesHide edge cases
Edge cases handled
c = [0, 0]i=0, i+2=2 out of range → jump 1 to i=1 = n-1. Returns 1.c = [0, 0, 0, 0, 0]All safe → 0→2→4. Two 2-jumps. Returns 2.c = [0, 1, 0, 1, 0]Thunderclouds force 2-jumps over each: 0→2→4. Returns 2.
Pitfalls
- Adding a c[i+1] == 0 check before a 2-jump — you never land on i+1, so it's irrelevant.
- Looping while i < n instead of i < n - 1 — overshoots the last cloud and over-counts.
- Forgetting the bounds check i + 2 < n — index out of bounds near the end.
Approach 2 of 2
Dynamic Programming — Minimum Jumps Table
1Hint 1Explore hintHide hint
Define dp[i] = minimum jumps to reach cloud i. What are the only clouds you could have jumped FROM to land on i?
2Hint 2Explore hintHide hint
You arrive at i from i-1 or i-2 (whichever are safe and in range): dp[i] = 1 + min(dp[i-1], dp[i-2]).
3Hint 3Explore hintHide hint
Set dp[0] = 0, skip thunderclouds (leave them unreachable / infinity), and return dp[n-1].
A · Core idea
Dynamic programming makes the optimality airtight without an exchange argument. Let dp[i] be the minimum number of jumps needed to reach cloud i, with dp[0] = 0.
The recurrence. You can only land on cloud i (a safe cloud) from cloud i − 1 or cloud i − 2. So dp[i] = 1 + min(dp[i − 1], dp[i − 2]), taking only those predecessors that are in range and reachable. Thunderclouds are never destinations, so we leave their dp as infinity (unreachable) — they simply don't contribute as predecessors when their own value is computed, but a 2-jump over them still works because dp[i] may draw from dp[i − 2] while dp[i − 1] is infinity.
Why it agrees with greedy. Because every edge has weight 1, the shortest path the DP finds equals the greedy move count. The DP is more general — it would still be correct if costs varied or if greedy were not obviously optimal — which is exactly why it's the safe choice to mention when you're unsure. For this specific problem greedy wins on space (O(1) vs O(n)), so state DP as the conceptual backbone and greedy as the optimised realisation.
Space reduction. Since dp[i] depends only on the previous two entries, you can collapse the array to two rolling variables and recover O(1) space — at which point it's essentially the greedy loop wearing a DP hat.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
c = [0, 0, 1, 0, 0, 1, 0]dp[0]
start
dp[0]=04C · Code with teaching comments
Reference implementation previewpublic int jumpingOnClouds(int[] c) { int n = c.length; int[] dp = new int[n]; final int INF = Integer.MAX_VALUE / 2; java.util.Arrays.fill(dp, INF);Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Minimum-jumps problems are shortest-path problems on a tiny graph: dp[i] = 1 + min over legal predecessors. Recognising 'fewest moves' as 'shortest path with unit edges' is the transferable idea — it scales to Jump Game II and grid BFS.
ComplexityO(n) time, O(n) space — Filling the table is a single left-to-right pass with O(1) work per cloud → O(n) time. The dp array of size n → O(n) space (reducible to O(1) by keeping only the last two values).
E · Edge cases and pitfalls5c = [0, 1, 0] — dp[1]=∞ (thundercloud), dp[2]=1+min(∞, dp[0]=0)=1. Returns 1 via a single 2-jump.Explore edge casesHide edge cases
Edge cases handled
c = [0, 1, 0]dp[1]=∞ (thundercloud), dp[2]=1+min(∞, dp[0]=0)=1. Returns 1 via a single 2-jump.c = [0, 0]dp[1]=1+dp[0]=1. Returns 1.
Pitfalls
- Using Integer.MAX_VALUE directly — adding 1 overflows; use MAX_VALUE/2 or a sentinel.
- Allowing dp[i] to be set for a thundercloud — it must stay unreachable.
- Forgetting the i >= 2 guard before reading dp[i-2].
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int jumpingOnClouds(int[] c) { int n = c.length; int i = 0; int jumps = 0; while (i < n - 1) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Blocking a 2-jump on the skipped cloud
A 2-jump lands on i+2 and never touches i+1, so c[i+1] is irrelevant. Checking it prevents valid jumps over thunderclouds.
Explore the code comparisonHide the code comparison
Blocking a 2-jump on the skipped cloud
A 2-jump lands on i+2 and never touches i+1, so c[i+1] is irrelevant. Checking it prevents valid jumps over thunderclouds.
Don't write this
if i + 2 < n and c[i + 1] == 0 and c[i + 2] == 0:
i += 2Write this instead
if i + 2 < n and c[i + 2] == 0:
i += 22Wrong loop bound overshoots the end
Looping while i < n lets the index step past the last cloud and counts a phantom extra jump. Stop at n - 1.
Explore the code comparisonHide the code comparison
Wrong loop bound overshoots the end
Looping while i < n lets the index step past the last cloud and counts a phantom extra jump. Stop at n - 1.
Don't write this
while (i < n) {
// ... jumps++
}Write this instead
while (i < n - 1) {
// ... jumps++
}3Integer overflow with INF sentinel (DP)
Using Integer.MAX_VALUE as INF and then adding 1 wraps to a large negative number, corrupting the min.
Explore the code comparisonHide the code comparison
Integer overflow with INF sentinel (DP)
Using Integer.MAX_VALUE as INF and then adding 1 wraps to a large negative number, corrupting the min.
Don't write this
final int INF = Integer.MAX_VALUE;
// ... dp[i] = INF + 1; // overflow!Write this instead
final int INF = Integer.MAX_VALUE / 2;
// ... dp[i] = best + 1; // safeRevise
Carry the pattern into the interview
Pattern to remember
Greedy max-step (jump 2 when safe, else 1)
Code pattern to memorize
i = 0, jumps = 0
while i < n - 1:
if i + 2 < n and c[i+2] == 0:
i += 2 # safe to skip
else:
i += 1
jumps += 1Rules to remember
- 1Thunderclouds (
c[i] == 1) can never be landed on — jumps must skip over them. - 2Prefer the 2-jump whenever
c[i+2] == 0; it covers more ground in the same one move. - 3A
2-jump is allowed even ifc[i+1] == 1— you fly over the thundercloud, you don't land on it. - 4Stop when you reach the last index
n − 1; the loop condition isi < n − 1, noti < n. - 5The first and last clouds are always safe (
0) per the constraints — no need to guard the start. - 6Every move costs exactly 1, whether you step 1 or 2 — minimise the number of moves, not distance.
Use this pattern when
- Reach the end of a line in the fewest steps with a small fixed step set
- A local 'take the biggest legal step' choice is provably globally optimal
- Obstacles forbid certain landing positions but the step set is tiny (1 or 2)
- You want O(1) space and a single forward pass
Choose another pattern when
- Step sizes vary per cell or are large/arbitrary → general DP / BFS (Jump Game II)
- You must count distinct paths, not the minimum → DP, not greedy
- Costs differ per cell → shortest-path / weighted DP
- Greedy choice can be locally good but globally bad → prove it or use DP
Interview takeaway
When the step set is {1, 2} and bigger steps are never harmful, greedily take the largest legal jump — it matches the DP optimum without a table. The same 'jump 2 when you safely can' instinct generalises to Jump Game and climbing-stairs-with-obstacles problems.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternGreedy maximal step on a line with a {1,2} step set. When every move costs the same and a longer legal jump never closes off a future option, greedily take the biggest legal jump — it equals the unit-edge shortest path (DP). Generalises to Jump Game and stair-climbing problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Jump Game IIComing soonStep sizes vary per cell — greedy BFS-by-range or DP for minimum jumps.
- Jump GameComing soonCan you reach the end at all? Greedy furthest-reach pass.
- Climbing StairsComing soonCount paths with steps {1,2} — same step set, but counting instead of minimising.
- Min Cost Climbing StairsComing soonWeighted version where greedy fails and DP is required.