Jump Game

🎯

Jump Game

mediumDPAmazonMicrosoftFacebook

Imagine you are playing a video game where you can jump forward on platforms, but each platform limits how far you can jump next. Can you reach the last platform?

💡 This problem tests your ability to reason about reachability in a sequence with constraints. Beginners often struggle because the problem looks like it can be solved greedily, but some inputs require dynamic programming to verify reachability.

📋

Problem Statement

Given an array of non-negative integers nums, where each element represents your maximum jump length at that position, determine if you can reach the last index starting from the first index. Return true if you can reach the last index, or false otherwise.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^5

💡

Example

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

Outputtrue

Start at index 0, jump 1 step to index 1, then jump 3 steps to the last index.

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

Outputfalse

You will always arrive at index 3 and cannot move further because nums[3] = 0.

• Single element array [0] → true (already at last index)
• Array with zeros blocking path [2,0,0] → false if zeros block all paths
• Array with large jumps at start [100,0,0,0] → true (jump directly to end)
• Array with all ones [1,1,1,1] → true (step by step reach end)

🔁

Why DP?

Why greedy fails:

Greedy fails when a local maximum jump leads to a dead end later. For example, in [3,2,1,0,4], greedy might jump to index 3 but cannot proceed further, missing that the last index is unreachable.

DP state:

dp[i] = true if you can reach the last index starting from index i, false otherwise.

Recurrence:dp[i] = OR over j in [i+1, i+nums[i]] of dp[j]

You can reach the end from i if you can jump to any position j reachable from i and reach the end from j.

⚠️

Common Mistakes

Not handling the base case when array length is 1

Returns false or errors instead of true

✅ Add explicit check or base case for single-element array

Assuming greedy always works without proof

Fails on inputs like [3,2,1,0,4]

✅ Understand problem constraints and test edge cases before using greedy

Not memoizing results in recursive approach

Exponential time and TLE

✅ Use a memo array to cache results

Iterating forwards in bottom-up DP

dp values not computed when needed, leading to incorrect results

✅ Iterate backwards from end to start

Updating maxReach after checking i > maxReach

Misses cases where current position is exactly maxReach

✅ Check i > maxReach before updating maxReach

🧠

Brute Force (Pure Recursion)

💡 This approach is the most straightforward and helps understand the problem's recursive nature, but it is inefficient due to repeated computations.

Intuition

From each position, try all possible jumps and recursively check if any path leads to the last index.

Algorithm

1. Start from index 0.
2. From current index, try all jumps within allowed range.
3. Recursively check if any jump leads to the last index.
4. Return true if any path reaches the end, else false.

💡 The recursion tree grows exponentially because each position tries multiple jumps, making it hard to track all paths.

Recurrence:canJump(i) = OR over j in [i+1, i+nums[i]] of canJump(j)

</>

Code

def canJump(nums):
    n = len(nums)
    def dfs(pos):
        if pos >= n - 1:
            return True
        furthest_jump = min(pos + nums[pos], n - 1)
        for next_pos in range(pos + 1, furthest_jump + 1):
            if dfs(next_pos):
                return True
        return False

# Driver code
if __name__ == '__main__':
    print(canJump([2,3,1,1,4]))  # True
    print(canJump([3,2,1,0,4]))  # False

Line Notes

def dfs(pos):Defines recursive function to check reachability from pos

if pos >= n - 1:Base case: reached or passed last index means success

for next_pos in range(pos + 1, furthest_jump + 1):Try all possible jumps from current position

if dfs(next_pos):If any jump leads to success, return True immediately

public class JumpGame {
    public static boolean canJump(int[] nums) {
        return dfs(nums, 0);
    }

    private static boolean dfs(int[] nums, int pos) {
        if (pos >= nums.length - 1) return true;
        int furthestJump = Math.min(pos + nums[pos], nums.length - 1);
        for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            if (dfs(nums, nextPos)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2,3,1,1,4})); // true
        System.out.println(canJump(new int[]{3,2,1,0,4})); // false
    }
}

Line Notes

private static boolean dfs(int[] nums, int pos)Recursive helper to check reachability from pos

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

for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++)Try all jumps from current position

if (dfs(nums, nextPos)) return true;Return true if any jump leads to success

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

bool dfs(const vector<int>& nums, int pos) {
    if (pos >= (int)nums.size() - 1) return true;
    int furthestJump = min(pos + nums[pos], (int)nums.size() - 1);
    for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos) {
        if (dfs(nums, nextPos)) return true;
    }
    return false;
}

int main() {
    vector<int> nums1 = {2,3,1,1,4};
    vector<int> nums2 = {3,2,1,0,4};
    cout << boolalpha << dfs(nums1, 0) << endl; // true
    cout << boolalpha << dfs(nums2, 0) << endl; // false
    return 0;
}

Line Notes

bool dfs(const vector<int>& nums, int pos)Recursive function to check reachability from pos

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

for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos)Try all possible jumps from current position

if (dfs(nums, nextPos)) return true;Return true if any jump leads to success

function canJump(nums) {
    const n = nums.length;
    function dfs(pos) {
        if (pos >= n - 1) return true;
        const furthestJump = Math.min(pos + nums[pos], n - 1);
        for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            if (dfs(nextPos)) return true;
        }
        return false;
    }
    return dfs(0);
}

// Test cases
console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Line Notes

function dfs(pos)Recursive helper to check reachability from pos

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

for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++)Try all jumps from current position

if (dfs(nextPos)) return true;Return true if any jump leads to success

⏱

Complexity

TimeO(2^n) in worst case

SpaceO(n) due to recursion stack

Each position can branch into multiple jumps, leading to exponential calls.

💡 For n=20, this could mean over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing states by caching results, drastically improving efficiency over brute force.

Intuition

Use recursion but store results of subproblems to avoid repeated work.

Algorithm

1. Initialize a memo array to store reachability results.
2. Start recursion from index 0.
3. If result for current index is cached, return it.
4. Try all jumps from current index and cache the result.

💡 Memoization prunes the recursion tree by remembering results, making the algorithm much faster.

Recurrence:dp[i] = OR over j in [i+1, i+nums[i]] of dp[j]

</>

Code

def canJump(nums):
    n = len(nums)
    memo = [None] * n
    def dfs(pos):
        if pos >= n - 1:
            return True
        if memo[pos] is not None:
            return memo[pos]
        furthest_jump = min(pos + nums[pos], n - 1)
        for next_pos in range(pos + 1, furthest_jump + 1):
            if dfs(next_pos):
                memo[pos] = True
                return True
        memo[pos] = False
        return False

# Driver code
if __name__ == '__main__':
    print(canJump([2,3,1,1,4]))  # True
    print(canJump([3,2,1,0,4]))  # False

Line Notes

memo = [None] * nInitialize memo array to cache results

if memo[pos] is not None:Return cached result if available

memo[pos] = TrueCache success result for current position

memo[pos] = FalseCache failure result if no jump leads to success

public class JumpGame {
    public static boolean canJump(int[] nums) {
        Boolean[] memo = new Boolean[nums.length];
        return dfs(nums, 0, memo);
    }

    private static boolean dfs(int[] nums, int pos, Boolean[] memo) {
        if (pos >= nums.length - 1) return true;
        if (memo[pos] != null) return memo[pos];
        int furthestJump = Math.min(pos + nums[pos], nums.length - 1);
        for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            if (dfs(nums, nextPos, memo)) {
                memo[pos] = true;
                return true;
            }
        }
        memo[pos] = false;
        return false;
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2,3,1,1,4})); // true
        System.out.println(canJump(new int[]{3,2,1,0,4})); // false
    }
}

Line Notes

Boolean[] memo = new Boolean[nums.length];Memo array to store results

if (memo[pos] != null) return memo[pos];Return cached result if exists

memo[pos] = true;Cache success for current position

memo[pos] = false;Cache failure if no path found

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

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

int main() {
    vector<int> nums1 = {2,3,1,1,4};
    vector<int> nums2 = {3,2,1,0,4};
    vector<int> memo1(nums1.size(), -1);
    vector<int> memo2(nums2.size(), -1);
    cout << boolalpha << dfs(nums1, 0, memo1) << endl; // true
    cout << boolalpha << dfs(nums2, 0, memo2) << endl; // false
    return 0;
}

Line Notes

vector<int>& memoMemo array passed by reference to cache results

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

memo[pos] = 1;Cache success for current position

memo[pos] = 0;Cache failure if no path found

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

// Test cases
console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Line Notes

const memo = new Array(n).fill(null);Initialize memo array to cache results

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

memo[pos] = true;Cache success for current position

memo[pos] = false;Cache failure if no path leads to success

⏱

Complexity

TimeO(n^2) worst case

SpaceO(n) for memo and recursion stack

Memoization avoids repeated calls but still may check up to n jumps per position.

💡 For n=1000, this means up to 1 million operations, which is acceptable.

Interview Verdict: Accepted

This approach is efficient enough for medium constraints and demonstrates DP principles.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from the end, avoiding recursion and making dependencies explicit.

Intuition

Start from the last index and move backwards, marking positions as reachable if they can jump to a reachable position.

Algorithm

1. Initialize a dp array of booleans with dp[last_index] = true.
2. Iterate from second last index down to 0.
3. For each index, check all reachable next positions.
4. If any next position is reachable, mark current as reachable.

💡 This approach makes dependencies clear and is easier to debug than recursion.

Recurrence:dp[i] = OR over j in [i+1, i+nums[i]] of dp[j]

</>

Code

def canJump(nums):
    n = len(nums)
    dp = [False] * n
    dp[-1] = True
    for i in range(n - 2, -1, -1):
        furthest_jump = min(i + nums[i], n - 1)
        for j in range(i + 1, furthest_jump + 1):
            if dp[j]:
                dp[i] = True
                break
    return dp[0]

# Driver code
if __name__ == '__main__':
    print(canJump([2,3,1,1,4]))  # True
    print(canJump([3,2,1,0,4]))  # False

Line Notes

dp = [False] * nInitialize dp array to track reachability

dp[-1] = TrueLast index is always reachable from itself

for i in range(n - 2, -1, -1):Fill dp from right to left

if dp[j]:If next position j is reachable, mark current i reachable

public class JumpGame {
    public static boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2,3,1,1,4})); // true
        System.out.println(canJump(new int[]{3,2,1,0,4})); // false
    }
}

Line Notes

boolean[] dp = new boolean[n];DP array to store reachability

dp[n - 1] = true;Last index is reachable

for (int i = n - 2; i >= 0; i--)Fill dp backwards

if (dp[j])If next position j is reachable, mark current i reachable

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

bool canJump(const vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n, false);
    dp[n - 1] = true;
    for (int i = n - 2; i >= 0; --i) {
        int furthestJump = min(i + nums[i], n - 1);
        for (int j = i + 1; j <= furthestJump; ++j) {
            if (dp[j]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[0];
}

int main() {
    vector<int> nums1 = {2,3,1,1,4};
    vector<int> nums2 = {3,2,1,0,4};
    cout << boolalpha << canJump(nums1) << endl; // true
    cout << boolalpha << canJump(nums2) << endl; // false
    return 0;
}

Line Notes

vector<bool> dp(n, false);DP array initialized to false

dp[n - 1] = true;Last index reachable by definition

for (int i = n - 2; i >= 0; --i)Fill dp from right to left

if (dp[j])If next position j is reachable, mark current i reachable

function canJump(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(false);
    dp[n - 1] = true;
    for (let i = n - 2; i >= 0; i--) {
        const furthestJump = Math.min(i + nums[i], n - 1);
        for (let j = i + 1; j <= furthestJump; j++) {
            if (dp[j]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[0];
}

// Test cases
console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Line Notes

const dp = new Array(n).fill(false);Initialize dp array for reachability

dp[n - 1] = true;Last index is reachable

for (let i = n - 2; i >= 0; i--)Fill dp backwards

if (dp[j])If next position j is reachable, mark current i reachable

⏱

Complexity

TimeO(n^2) worst case

SpaceO(n) for dp array

For each index, we check up to nums[i] next positions, leading to quadratic time.

💡 For n=1000, this is about 1 million operations, which is acceptable but can be improved.

Interview Verdict: Accepted

This approach is efficient and easy to understand, suitable for interviews.

🧠

Greedy Approach (Optimal)

💡 Greedy is the most efficient approach, using a single pass to track the furthest reachable index, but it requires understanding why it works.

Intuition

Keep track of the furthest index reachable so far. If at any point the current index is beyond this, return false.

Algorithm

1. Initialize maxReach to 0.
2. Iterate through the array indices.
3. If current index is greater than maxReach, return false (cannot reach here).
4. Update maxReach to max(maxReach, i + nums[i]).
5. If maxReach reaches or passes last index, return true.

💡 This approach efficiently tracks reachability without exploring all paths.

Recurrence:maxReach = max(maxReach, i + nums[i])

</>

Code

def canJump(nums):
    maxReach = 0
    n = len(nums)
    for i in range(n):
        if i > maxReach:
            return False
        maxReach = max(maxReach, i + nums[i])
        if maxReach >= n - 1:
            return True
    return False

# Driver code
if __name__ == '__main__':
    print(canJump([2,3,1,1,4]))  # True
    print(canJump([3,2,1,0,4]))  # False

Line Notes

maxReach = 0Initialize furthest reachable index

for i in range(n):Iterate through each position

if i > maxReach:If current position is beyond reach, fail early

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

public class JumpGame {
    public static boolean canJump(int[] nums) {
        int maxReach = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= n - 1) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2,3,1,1,4})); // true
        System.out.println(canJump(new int[]{3,2,1,0,4})); // false
    }
}

Line Notes

int maxReach = 0;Track furthest reachable index

for (int i = 0; i < n; i++)Iterate through positions

if (i > maxReach) return false;Fail if current index unreachable

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

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

bool canJump(const vector<int>& nums) {
    int maxReach = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        if (i > maxReach) return false;
        maxReach = max(maxReach, i + nums[i]);
        if (maxReach >= n - 1) return true;
    }
    return false;
}

int main() {
    vector<int> nums1 = {2,3,1,1,4};
    vector<int> nums2 = {3,2,1,0,4};
    cout << boolalpha << canJump(nums1) << endl; // true
    cout << boolalpha << canJump(nums2) << endl; // false
    return 0;
}

Line Notes

int maxReach = 0;Initialize furthest reachable index

for (int i = 0; i < n; ++i)Iterate through each position

if (i > maxReach) return false;If current index unreachable, return false

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

function canJump(nums) {
    let maxReach = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= n - 1) return true;
    }
    return false;
}

// Test cases
console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Line Notes

let maxReach = 0;Initialize furthest reachable index

for (let i = 0; i < n; i++)Iterate through positions

if (i > maxReach) return false;Fail if current index unreachable

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

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space.

💡 For n=10^5, this is very efficient and suitable for large inputs.

Interview Verdict: Accepted

This is the optimal solution and the one to implement in interviews for efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, implement the greedy approach unless asked otherwise. Understand brute force and DP for conceptual clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes	N/A	Mention only - never code
2. Top-Down DP with Memoization	O(n^2)	O(n)	Possible but less than brute force	Yes	Good to explain DP concepts
3. Bottom-Up DP (Tabulation)	O(n^2)	O(n)	No	Yes	Good alternative to recursion
4. Greedy Approach (Optimal)	O(n)	O(1)	No	No (only boolean answer)	Implement in interviews for efficiency

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to use each. Start with brute force to grasp the problem, then optimize progressively.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up DP as an iterative alternative.Step 5: Finally, explain the greedy approach as the optimal solution.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your problem-solving skills, understanding of DP vs greedy, and ability to optimize from naive to optimal solutions.

Common Follow-ups

• Can you find the minimum number of jumps to reach the end? → Use DP with tracking jumps.
• What if you want to return the actual path? → Store predecessors during DP.
• How does the greedy approach guarantee correctness? → Explain why local maxReach suffices.
• What if jumps can be backward? → Problem becomes more complex, possibly BFS.

💡 These follow-ups test deeper understanding and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves jumping or moving forward with constraints; 2) Need to check reachability; 3) Input is linear array; 4) Optimal substructure and overlapping subproblems exist.

Signature Phrases

maximum jump length at each positioncan you reach the last indexjump forward

NOT This Pattern When

Problems involving arbitrary graph traversal or backtracking without linear constraints.

Similar Problems

Jump Game II - find minimum jumps instead of boolean reachabilityMinimum Number of Jumps to Reach End - similar DP approachFrog Jump - jump with variable constraints and positions

Practice

1. Identify the bug in the following code snippet for calculating max profit from one stock transaction:

medium

A. Line 2: initializing min_price with prices[0] instead of infinity

B. Line 4: updating max_profit before updating min_price causes incorrect profit calculation

C. Line 5: the if condition should be prices[i] <= min_price

D. Line 6: returning max_profit instead of min_price

Solution

1. Step 1: Analyze update order in loop

   max_profit is updated before min_price, so profit may be calculated using outdated min_price.

2. Step 2: Identify correct update order

   min_price must be updated first to ensure profit calculation uses the lowest price so far.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping update order fixes incorrect profit calculation [OK]

Hint: Update min_price before max_profit in loop [OK]

Common Mistakes:

• Updating max_profit before min_price
• Using <= instead of < causing no difference
• Incorrect initialization rarely causes bugs here

2. Consider the following buggy code for maxProfit with cooldown. Which line contains the subtle bug that causes incorrect profit calculation on some inputs?

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    hold = -prices[0]
    cool = 0
    free = 0
    for i in range(1, n):
        prev_hold = hold
        hold = max(hold, free - prices[i])
        free = max(free, cool)
        cool = hold + prices[i]  # Bug here
    return max(cool, free)

medium

A. Line assigning cool = hold + prices[i]

B. Line assigning free = max(free, cool)

C. Line assigning hold = max(hold, free - prices[i])

D. Line initializing hold = -prices[0]

Solution

1. Step 1: Identify correct cooldown update

   Cooldown profit must be previous hold plus current price (selling today), so cool = prev_hold + prices[i].

2. Step 2: Spot the bug

   Code uses current hold instead of prev_hold, which may have been updated this iteration, causing incorrect profit calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using hold instead of prev_hold breaks cooldown logic [OK]

Hint: Cooldown uses previous hold, not updated hold [OK]

Common Mistakes:

• Using current hold instead of prev_hold for cooldown
• Ignoring cooldown day after selling

3. 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

4. What is the time complexity of the optimal space-optimized bottom-up dynamic programming solution for the decoding ways problem, and why?

medium

A. O(n) but with O(n) auxiliary space for dp array

B. O(n^2) because each position checks all previous positions

C. O(2^n) due to recursive branching without memoization

D. O(n) because each character is processed once with constant checks

Solution

1. Step 1: Analyze loop iterations

   The code iterates through the string once, processing each character exactly once.

2. Step 2: Check operations per iteration

   Each iteration performs constant time checks for single and two-digit validity, no nested loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear scan with constant work per step -> O(n) time [OK]

Hint: One pass with constant work per character -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing recursion without memoization complexity

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