Jump Game II (Min Jumps)

🎯

Jump Game II (Min Jumps)

mediumDPAmazonGoogle

Imagine you are playing a video game where you must jump across platforms to reach the end with the fewest jumps possible. Each platform lets you jump a certain maximum distance forward.

💡 This problem asks for the minimum number of jumps to reach the end of an array where each element represents max jump length. Beginners often struggle because the greedy approach can fail in some cases, and understanding the DP formulation requires grasping overlapping subproblems and optimal substructure.

📋

Problem Statement

Given an array of non-negative integers nums, where each element represents your maximum jump length at that position, return the minimum number of jumps required to reach the last index starting from the first index. You can assume you can always reach the last index.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^5It is guaranteed that you can reach the last index.

💡

Example

Input"[2,3,1,1,4]"

Output2

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input"[2,3,0,1,4]"

Output2

Jump from index 0 to 1, then from 1 to 4.

• Single element array [0] → 0 jumps needed
• Array with all ones [1,1,1,1] → jumps equal to length-1
• Array with zero in middle but reachable [3,2,1,0,4] → guaranteed reachable so no zero trap
• Large jumps at start [10,1,1,1,1] → only 1 jump needed

🔁

Why DP?

Why greedy fails:

Greedy fails when a locally optimal jump doesn't lead to a global minimum. For example, in [2,3,1,1,4], greedy might pick the first jump to index 2 (max jump from 0), but the optimal is to jump to index 1 first, then jump 3 steps to the end.

DP state:

dp[i] = minimum number of jumps needed to reach index i from the start.

Recurrence:dp[i] = min(dp[j] + 1) for all j < i where j + nums[j] >= i

To get to position i, find all positions j that can jump to i, and pick the one with the fewest jumps plus one more jump.

⚠️

Common Mistakes

Using greedy approach without understanding when it fails

Incorrect minimum jumps in some test cases

✅ Explain and prove greedy correctness or fallback to DP

Not handling base case when array length is 1

Returns wrong answer or errors

✅ Check if start is already at last index and return 0

Forgetting to update dp array properly in bottom-up DP

dp values remain infinity, leading to wrong answer

✅ Ensure dp[j] is updated with min(dp[j], dp[i] + 1)

Stack overflow in brute force recursion for large inputs

Runtime error due to deep recursion

✅ Use memoization or iterative DP to avoid deep recursion

Not limiting furthest jump to array bounds

Index out of range errors

✅ Use min(pos + nums[pos], n - 1) to limit jumps

🧠

Brute Force (Pure Recursion)

💡 Brute force explores all jump paths recursively to find the minimum jumps. It is simple to understand but inefficient due to repeated calculations.

Intuition

From each position, try all possible jumps and recursively find the minimum jumps to reach the end.

Algorithm

1. Start at index 0.
2. From current index, try all jumps within allowed range.
3. Recursively compute minimum jumps from each reachable index.
4. Return the minimum jumps found plus one for the current jump.

💡 This approach is intuitive but leads to exponential calls because it tries every jump path without remembering results.

Recurrence:dp[i] = min(dp[j] + 1) for all j > i where i + nums[i] >= j

</>

Code

def jump(nums):
    n = len(nums)
    def dfs(pos):
        if pos >= n - 1:
            return 0
        min_jumps = float('inf')
        furthest_jump = min(pos + nums[pos], n - 1)
        for next_pos in range(pos + 1, furthest_jump + 1):
            jumps = dfs(next_pos)
            if jumps != float('inf'):
                min_jumps = min(min_jumps, jumps + 1)
        return min_jumps
    return dfs(0)

# Example usage
if __name__ == '__main__':
    print(jump([2,3,1,1,4]))  # Output: 2

Line Notes

def dfs(pos):Defines recursive function to compute min jumps from position pos

if pos >= n - 1:Base case: reached or passed last index, no more jumps needed

for next_pos in range(pos + 1, furthest_jump + 1):Try all reachable next positions from current pos

min_jumps = min(min_jumps, jumps + 1)Update minimum jumps considering jump from pos to next_pos

public class Solution {
    public int jump(int[] nums) {
        return dfs(nums, 0);
    }
    private int dfs(int[] nums, int pos) {
        if (pos >= nums.length - 1) return 0;
        int minJumps = Integer.MAX_VALUE;
        int furthestJump = Math.min(pos + nums[pos], nums.length - 1);
        for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            int jumps = dfs(nums, nextPos);
            if (jumps != Integer.MAX_VALUE) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }
        return minJumps;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.jump(new int[]{2,3,1,1,4})); // Output: 2
    }
}

Line Notes

public int jump(int[] nums)Entry point calling recursive dfs from index 0

if (pos >= nums.length - 1) return 0;Base case: reached or beyond last index

for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++)Try all reachable next positions

minJumps = Math.min(minJumps, jumps + 1);Update minimum jumps with jump from pos to nextPos

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dfs(const vector<int>& nums, int pos) {
    if (pos >= (int)nums.size() - 1) return 0;
    int minJumps = INT_MAX;
    int furthestJump = min(pos + nums[pos], (int)nums.size() - 1);
    for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos) {
        int jumps = dfs(nums, nextPos);
        if (jumps != INT_MAX) {
            minJumps = min(minJumps, jumps + 1);
        }
    }
    return minJumps;
}

int jump(vector<int>& nums) {
    return dfs(nums, 0);
}

int main() {
    vector<int> nums = {2,3,1,1,4};
    cout << jump(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int dfs(const vector<int>& nums, int pos)Recursive function to find min jumps from pos

if (pos >= (int)nums.size() - 1) return 0;Base case: reached or passed last index

for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos)Try all reachable next positions

minJumps = min(minJumps, jumps + 1);Update minimum jumps with jump from pos to nextPos

function jump(nums) {
    const n = nums.length;
    function dfs(pos) {
        if (pos >= n - 1) return 0;
        let minJumps = Infinity;
        const furthestJump = Math.min(pos + nums[pos], n - 1);
        for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            const jumps = dfs(nextPos);
            if (jumps !== Infinity) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }
        return minJumps;
    }
    return dfs(0);
}

console.log(jump([2,3,1,1,4])); // Output: 2

Line Notes

function dfs(pos)Recursive helper to compute min jumps from pos

if (pos >= n - 1) return 0;Base case: reached or passed last index

for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++)Try all reachable next positions

minJumps = Math.min(minJumps, jumps + 1);Update minimum jumps with jump from pos to nextPos

⏱

Complexity

TimeO(2^n) in worst case due to exploring all jump paths

SpaceO(n) due to recursion stack depth

Each position tries all reachable next positions recursively, leading to exponential calls.

💡 For n=20, this means potentially over a million recursive calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate optimization.

🧠

Top-Down DP with Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency over brute force.

Intuition

Use recursion but store minimum jumps for each index once computed, so repeated calls return cached results.

Algorithm

1. Initialize a memo array to store min jumps for each index.
2. Define recursive function that returns memoized result if available.
3. From current index, try all reachable next positions recursively.
4. Store and return the minimum jumps found plus one.

💡 Memoization turns exponential recursion into polynomial by caching results.

Recurrence:dp[i] = min(dp[j] + 1) for all j > i where i + nums[i] >= j

</>

Code

def jump(nums):
    n = len(nums)
    memo = [-1] * n
    def dfs(pos):
        if pos >= n - 1:
            return 0
        if memo[pos] != -1:
            return memo[pos]
        min_jumps = float('inf')
        furthest_jump = min(pos + nums[pos], n - 1)
        for next_pos in range(pos + 1, furthest_jump + 1):
            jumps = dfs(next_pos)
            if jumps != float('inf'):
                min_jumps = min(min_jumps, jumps + 1)
        memo[pos] = min_jumps
        return min_jumps
    return dfs(0)

# Example usage
if __name__ == '__main__':
    print(jump([2,3,1,1,4]))  # Output: 2

Line Notes

memo = [-1] * nInitialize memo array with -1 indicating uncomputed states

if memo[pos] != -1:Return cached result if already computed

memo[pos] = min_jumpsCache computed minimum jumps for current position

return memo[pos]Return cached or newly computed result

import java.util.Arrays;
public class Solution {
    private int[] memo;
    public int jump(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return dfs(nums, 0);
    }
    private int dfs(int[] nums, int pos) {
        if (pos >= nums.length - 1) return 0;
        if (memo[pos] != -1) return memo[pos];
        int minJumps = Integer.MAX_VALUE;
        int furthestJump = Math.min(pos + nums[pos], nums.length - 1);
        for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            int jumps = dfs(nums, nextPos);
            if (jumps != Integer.MAX_VALUE) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }
        memo[pos] = minJumps;
        return minJumps;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.jump(new int[]{2,3,1,1,4})); // Output: 2
    }
}

Line Notes

memo = new int[nums.length];Create memo array to cache results

Arrays.fill(memo, -1);Initialize memo with -1 to mark unvisited states

if (memo[pos] != -1) return memo[pos];Return cached result if available

memo[pos] = minJumps;Store computed minimum jumps for position

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dfs(const vector<int>& nums, int pos, vector<int>& memo) {
    if (pos >= (int)nums.size() - 1) return 0;
    if (memo[pos] != -1) return memo[pos];
    int minJumps = INT_MAX;
    int furthestJump = min(pos + nums[pos], (int)nums.size() - 1);
    for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos) {
        int jumps = dfs(nums, nextPos, memo);
        if (jumps != INT_MAX) {
            minJumps = min(minJumps, jumps + 1);
        }
    }
    memo[pos] = minJumps;
    return minJumps;
}

int jump(vector<int>& nums) {
    vector<int> memo(nums.size(), -1);
    return dfs(nums, 0, memo);
}

int main() {
    vector<int> nums = {2,3,1,1,4};
    cout << jump(nums) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> memo(nums.size(), -1);Initialize memo vector with -1 for unvisited states

if (memo[pos] != -1) return memo[pos];Return cached result if computed

memo[pos] = minJumps;Cache minimum jumps for current position

return memo[pos];Return cached or computed result

function jump(nums) {
    const n = nums.length;
    const memo = new Array(n).fill(-1);
    function dfs(pos) {
        if (pos >= n - 1) return 0;
        if (memo[pos] !== -1) return memo[pos];
        let minJumps = Infinity;
        const furthestJump = Math.min(pos + nums[pos], n - 1);
        for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            const jumps = dfs(nextPos);
            if (jumps !== Infinity) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }
        memo[pos] = minJumps;
        return minJumps;
    }
    return dfs(0);
}

console.log(jump([2,3,1,1,4])); // Output: 2

Line Notes

const memo = new Array(n).fill(-1);Create memo array initialized to -1 for unvisited states

if (memo[pos] !== -1) return memo[pos];Return cached result if available

memo[pos] = minJumps;Cache computed minimum jumps for position

return memo[pos];Return cached or newly computed result

⏱

Complexity

TimeO(n^2) because each index may check all reachable next indices

SpaceO(n) for memo array and recursion stack

Memoization avoids repeated calls but still may check many jumps per index.

💡 For n=1000, this means up to 1 million operations, which is feasible but not optimal.

Interview Verdict: Accepted but can be slow for large inputs

Memoization improves brute force to polynomial time but still not optimal for very large arrays.

🧠

Bottom-Up DP (Tabulation)

💡 Bottom-up DP builds the solution iteratively from the start, filling a dp array with minimum jumps to each index, avoiding recursion overhead.

Intuition

Start from index 0 with 0 jumps, then for each reachable index update the minimum jumps needed.

Algorithm

1. Initialize dp array with infinity except dp[0] = 0.
2. Iterate over each index i from 0 to n-1.
3. For each i, update dp[j] for all j reachable from i.
4. Return dp[n-1] as the minimum jumps to reach the end.

💡 This approach systematically computes minimum jumps for all positions in order.

Recurrence:dp[i] = min(dp[j] + 1) for all j < i where j + nums[j] >= i

</>

Code

def jump(nums):
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(n):
        furthest_jump = min(i + nums[i], n - 1)
        for j in range(i + 1, furthest_jump + 1):
            dp[j] = min(dp[j], dp[i] + 1)
    return dp[-1]

# Example usage
if __name__ == '__main__':
    print(jump([2,3,1,1,4]))  # Output: 2

Line Notes

dp = [float('inf')] * nInitialize dp array with infinity representing unreachable states

dp[0] = 0Starting position requires zero jumps

for i in range(n):Iterate over each position to update reachable indices

dp[j] = min(dp[j], dp[i] + 1)Update minimum jumps to reach j from i

import java.util.Arrays;
public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int furthestJump = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (dp[i] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n - 1];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.jump(new int[]{2,3,1,1,4})); // Output: 2
    }
}

Line Notes

int[] dp = new int[n];Create dp array to store minimum jumps

Arrays.fill(dp, Integer.MAX_VALUE);Initialize dp with max value to represent unreachable

dp[0] = 0;Zero jumps needed at start

dp[j] = Math.min(dp[j], dp[i] + 1);Update dp[j] with minimum jumps from i

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int jump(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        int furthestJump = min(i + nums[i], n - 1);
        for (int j = i + 1; j <= furthestJump; ++j) {
            if (dp[i] != INT_MAX) {
                dp[j] = min(dp[j], dp[i] + 1);
            }
        }
    }
    return dp[n - 1];
}

int main() {
    vector<int> nums = {2,3,1,1,4};
    cout << jump(nums) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> dp(n, INT_MAX);Initialize dp vector with max int to represent unreachable

dp[0] = 0;Start position requires zero jumps

for (int i = 0; i < n; ++i)Iterate over each index to update reachable positions

dp[j] = min(dp[j], dp[i] + 1);Update minimum jumps to reach j from i

function jump(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;
    for (let i = 0; i < n; i++) {
        const furthestJump = Math.min(i + nums[i], n - 1);
        for (let j = i + 1; j <= furthestJump; j++) {
            if (dp[i] !== Infinity) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
    }
    return dp[n - 1];
}

console.log(jump([2,3,1,1,4])); // Output: 2

Line Notes

const dp = new Array(n).fill(Infinity);Initialize dp array with Infinity for unreachable states

dp[0] = 0;Zero jumps needed at start

for (let i = 0; i < n; i++)Iterate over each index to update reachable indices

dp[j] = Math.min(dp[j], dp[i] + 1);Update minimum jumps to reach j from i

⏱

Complexity

TimeO(n^2) due to nested loops updating dp

SpaceO(n) for dp array

For each index, we update all reachable indices, leading to quadratic time.

💡 For n=1000, this means about 1 million operations, which is acceptable but not ideal.

Interview Verdict: Accepted but can be slow for large inputs

Bottom-up DP is easier to understand and debug than recursion but still quadratic time.

🧠

Greedy Approach (Optimal)

💡 Greedy approach tracks the current reachable range and the next reachable range to jump optimally in linear time.

Intuition

At each step, jump to the position that extends the furthest reachable index, minimizing jumps.

Algorithm

1. Initialize jumps, current_end, and furthest variables.
2. Iterate through the array updating the furthest reachable index.
3. When reaching current_end, increment jumps and update current_end to furthest.
4. Return jumps after iteration.

💡 This approach uses a linear scan and updates jump count only when the current jump range ends.

Recurrence:Not a classical DP recurrence; uses greedy range updates instead.

</>

Code

def jump(nums):
    n = len(nums)
    jumps = 0
    current_end = 0
    furthest = 0
    for i in range(n - 1):
        furthest = max(furthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = furthest
    return jumps

# Example usage
if __name__ == '__main__':
    print(jump([2,3,1,1,4]))  # Output: 2

Line Notes

jumps = 0Initialize jump count

current_end = 0End of current jump range

furthest = 0Furthest reachable index in next jump

if i == current_end:When current jump range ends, increment jumps and update range

public class Solution {
    public int jump(int[] nums) {
        int jumps = 0, currentEnd = 0, furthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            furthest = Math.max(furthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = furthest;
            }
        }
        return jumps;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.jump(new int[]{2,3,1,1,4})); // Output: 2
    }
}

Line Notes

int jumps = 0Initialize jump count

int currentEnd = 0End of current jump range

furthest = Math.max(furthest, i + nums[i]);Update furthest reachable index

if (i == currentEnd)When current jump range ends, increment jumps and update range

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int jump(vector<int>& nums) {
    int jumps = 0, currentEnd = 0, furthest = 0;
    for (int i = 0; i < (int)nums.size() - 1; ++i) {
        furthest = max(furthest, i + nums[i]);
        if (i == currentEnd) {
            ++jumps;
            currentEnd = furthest;
        }
    }
    return jumps;
}

int main() {
    vector<int> nums = {2,3,1,1,4};
    cout << jump(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int jumps = 0Initialize jump count

int currentEnd = 0End of current jump range

furthest = max(furthest, i + nums[i]);Update furthest reachable index

if (i == currentEnd)When current jump range ends, increment jumps and update range

function jump(nums) {
    let jumps = 0, currentEnd = 0, furthest = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        furthest = Math.max(furthest, i + nums[i]);
        if (i === currentEnd) {
            jumps++;
            currentEnd = furthest;
        }
    }
    return jumps;
}

console.log(jump([2,3,1,1,4])); // Output: 2

Line Notes

let jumps = 0Initialize jump count

let currentEnd = 0End of current jump range

furthest = Math.max(furthest, i + nums[i]);Update furthest reachable index

if (i === currentEnd)When current jump range ends, increment jumps and update range

⏱

Complexity

TimeO(n) because we scan the array once

SpaceO(1) constant extra space

We track ranges and jumps in a single pass without extra arrays.

💡 For n=10^5, this means 100,000 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Greedy approach is best for interviews due to optimal time and space. Memoization and bottom-up DP are good for understanding and debugging. Brute force is only for conceptual introduction.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down DP with Memoization	O(n^2)	O(n) memo + recursion stack	Possible for large n	Yes with path tracking	Good to mention and code if comfortable
3. Bottom-Up DP (Tabulation)	O(n^2)	O(n)	No	Yes with path tracking	Good for clarity, but slower than greedy
4. Greedy Approach (Optimal)	O(n)	O(1)	No	No (without extra work)	Best approach to implement in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to use each. Read before every mock interview to build confidence.

How to Present

Clarify problem constraints and assumptions.Explain brute force approach to show understanding.Introduce memoization to optimize recursion.Present bottom-up DP for iterative clarity.Finally, explain greedy approach as optimal solution.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of DP concepts, ability to optimize naive solutions, and knowledge of greedy algorithms where applicable.

Common Follow-ups

• What if you want to return the actual jump path? → Use DP with path reconstruction.
• Can you solve it in O(n) time? → Yes, using the greedy approach.

💡 These follow-ups test your ability to extend solutions and optimize further.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimum steps/jumps to reach end; 2) Each position has a max jump length; 3) Overlapping subproblems exist; 4) Greedy might be possible but needs proof.

Signature Phrases

minimum number of jumpsreach the last indexmaximum jump length at that position

NOT This Pattern When

Problems asking only if reachable (yes/no) without minimum steps are Jump Game I style, not minimum jumps.

Similar Problems

Jump Game I - feasibility check if last index reachableMinimum Number of Refueling Stops - similar greedy vs DP tradeoffCoin Change - classic DP with minimum operations

Practice

1. Given the following code, what is the value of max_profit after the loop finishes when prices = [3, 2, 6]?

easy

A. 0

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace iteration i=1 with price=2

   min_price updated from 3 to 2, max_profit remains 0.

2. Step 2: Trace iteration i=2 with price=6

   max_profit updated to max(0, 6 - 2) = 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Max profit is 4 from buying at 2 and selling at 6 [OK]

Hint: Update min price before max profit each iteration [OK]

Common Mistakes:

• Confusing indices and off-by-one errors
• Updating max profit before min price
• Returning intermediate instead of final max profit

2. Consider the following code snippet implementing the optimal decoding count algorithm. What is the value of curr after the second iteration of the loop when input s = "226"?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Trace first iteration (i=1)

   For s[1] = '2', curr = prev1 (1) + prev2 (1) = 2, prev2=1, prev1=2 after update.

2. Step 2: Trace second iteration (i=2)

   For s[2] = '6', curr starts at 0, s[2] != '0' so curr += prev1 (2), two_digit = 26 in [10,26], curr += prev2 (1), total curr = 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   At second iteration curr=3 matches expected decoding count [OK]

Hint: Add prev1 if single digit valid, add prev2 if two-digit valid [OK]

Common Mistakes:

• Off-by-one in loop index or incorrect curr update

3. Consider the following Python code implementing the optimal solution for the House Robber II problem. What is the final output when the input is [2, 3, 2]?

def rob_linear(nums, start, end):
    prev, curr = 0, 0
    for i in range(start, end + 1):
        prev, curr = curr, max(curr, prev + nums[i])
    return curr

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))

print(rob([2,3,2]))

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace rob_linear(nums, 0, 1)

   nums[0]=2, nums[1]=3 Iteration i=0: prev=0, curr=0 -> prev=0, curr=max(0,0+2)=2 Iteration i=1: prev=2, curr=max(2,0+3)=3 Return 3

2. Step 2: Trace rob_linear(nums, 1, 2)

   nums[1]=3, nums[2]=2 Iteration i=1: prev=0, curr=0 -> prev=0, curr=max(0,0+3)=3 Iteration i=2: prev=3, curr=max(3,0+2)=3 Return 3 Max(3,3) = 3

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both cases yield 3, final output is 3 [OK]

Hint: Trace both linear cases and pick max [OK]

Common Mistakes:

• Off-by-one in loop range
• Confusing which subarray to use
• Incorrect max calculation

4. What is the time complexity of the space-optimized bottom-up DP solution for the Best Time -- K Transactions problem, given n days and k transactions?

medium

A. O(n * 2^k) due to exponential state combinations

B. O(k) because we only keep arrays of size k regardless of n

C. O(n * k) because for each day we update k states in reverse order

D. O(n^2) since for each day we scan all previous days

Solution

1. Step 1: Identify loops in the code

   Outer loop runs over n days, inner loop runs over k transactions in reverse order.

2. Step 2: Calculate complexity

   Each iteration does O(1) work, total O(n * k). No recursion stack or nested scanning over days.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Code has two nested loops: days and transactions [OK]

Hint: Two nested loops: days and transactions [OK]

Common Mistakes:

• Assuming exponential due to recursion
• Confusing with O(n^2) from naive solutions

5. Suppose the House Robber problem is modified so you can rob the same house multiple times (unlimited reuse). Which of the following changes to the algorithm correctly computes the maximum amount you can rob?

hard

A. Use the original DP but allow robbing adjacent houses since reuse is allowed

B. Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement

C. Use a new DP where dp[i] = max(dp[i-1], dp[i-2] + nums[i]) but allow revisiting dp[i] multiple times

D. Modify DP to consider robbing the current house plus the best solution including the current house again (i.e., dp[i] = max(dp[i-1], dp[i] + nums[i]))

Solution

1. Step 1: Understand problem change

   Allowing unlimited reuse means we can rob the same house multiple times, similar to unbounded knapsack.

2. Step 2: Identify correct DP formulation

   Unbounded knapsack style DP updates dp[i] considering dp[i - 1] + nums[i] repeatedly until stable.

3. Step 3: Evaluate options

   Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement correctly describes iterative updates until no improvement, matching unbounded knapsack logic.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Original adjacency constraints no longer apply; unbounded knapsack DP fits [OK]

Hint: Reuse means unbounded knapsack, not original adjacency DP [OK]

Common Mistakes:

• Trying to reuse original adjacency DP
• Ignoring repeated state updates