House Robber II (Circular)

🎯

House Robber II (Circular)

mediumDPAmazonGoogle

Imagine a thief planning to rob houses arranged in a circle. Because the first and last houses are neighbors, robbing both triggers an alarm. How can the thief maximize loot without alerting the police?

💡 This problem extends the classic linear house robber problem by adding a circular constraint, making it trickier. Beginners often struggle because the circular arrangement breaks the straightforward linear DP approach, requiring careful case splitting.

📋

Problem Statement

You are a professional robber planning to rob houses along a street arranged in a circle. Each house has a certain amount of money stashed. Adjacent houses have security systems connected, so robbing two adjacent houses will trigger an alarm. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob without alerting the police.

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

💡

Example

Input"[2,3,2]"

Output3

Rob house 2 (money = 3), cannot rob house 1 and 3 together because they are adjacent in a circle.

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

Output4

Rob houses 1 and 3 (1-based indexing), total amount = 1 + 3 = 4.

Input"[0]"

Output0

Only one house with zero money, so max loot is 0.

• Single house → must rob that house
• Two houses with different amounts → rob the richer one
• All houses have zero money → result is zero
• Large input size (10^5 houses) → solution must be efficient

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the house with the maximum immediate loot fails because it may force skipping houses with larger combined loot later. For example, in [2,3,2], greedy picks 3, but considering circular adjacency, robbing house 1 and 3 is invalid, so greedy fails to maximize.

DP state:

dp[i] represents the maximum amount of money that can be robbed from the first i houses in a linear arrangement without alerting the police.

Recurrence:dp[i] = max(dp[i-1], dp[i-2] + nums[i])

At house i, either skip it and keep previous max dp[i-1], or rob it and add its loot to dp[i-2]. Choose the better option.

⚠️

Common Mistakes

Not handling circular constraint by splitting into two cases

Incorrectly robbing first and last house together, causing wrong answer

✅ Solve two linear cases excluding first or last house and take max

Using brute force recursion without memoization

Time limit exceeded on large inputs

✅ Add memoization or use iterative DP

Incorrect base cases in DP

Index errors or wrong results for small inputs

✅ Carefully initialize dp for 0 or 1 house cases

Confusing indices when excluding first or last house

Off-by-one errors and wrong subarray ranges

✅ Explicitly define start and end indices for linear subproblems

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient.

Intuition

Try robbing each house or skipping it, recursively exploring all combinations while respecting the circular constraint by splitting into two linear cases.

Algorithm

1. Define a recursive function to compute max loot for a linear range of houses.
2. Since houses are in a circle, solve two linear cases: excluding first house and excluding last house.
3. Return the maximum of the two cases.
4. Base cases handle empty or single house ranges.

💡 The recursion explores all subsets but is inefficient due to repeated calculations and exponential calls.

Recurrence:rob(i) = max(rob(i-1), rob(i-2) + nums[i])

</>

Code

def rob_linear(nums, start, end):
    if start > end:
        return 0
    if start == end:
        return nums[start]
    return max(rob_linear(nums, start, end - 1), rob_linear(nums, start, end - 2) + nums[end])

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))

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

Line Notes

def rob_linear(nums, start, end):Defines helper to compute max loot in linear subarray

if start > end:Base case: no houses left to rob

return max(rob_linear(nums, start, end - 1), rob_linear(nums, start, end - 2) + nums[end])Choose to skip or rob current house

return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))Solve two linear cases excluding first or last house

public class Solution {
    public int robLinear(int[] nums, int start, int end) {
        if (start > end) return 0;
        if (start == end) return nums[start];
        return Math.max(robLinear(nums, start, end - 1), robLinear(nums, start, end - 2) + nums[end]);
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rob(new int[]{2,3,2})); // Output: 3
    }
}

Line Notes

public int robLinear(int[] nums, int start, int end)Helper method for linear subproblem

if (start > end) return 0;Base case: no houses to rob

return Math.max(robLinear(nums, start, end - 1), robLinear(nums, start, end - 2) + nums[end]);Choose skip or rob current house

return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));Solve two linear cases excluding first or last house

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

int robLinear(const vector<int>& nums, int start, int end) {
    if (start > end) return 0;
    if (start == end) return nums[start];
    return max(robLinear(nums, start, end - 1), robLinear(nums, start, end - 2) + nums[end]);
}

int rob(const vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}

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

Line Notes

int robLinear(const vector<int>& nums, int start, int end)Helper for linear subproblem

if (start > end) return 0;Base case: no houses

return max(robLinear(nums, start, end - 1), robLinear(nums, start, end - 2) + nums[end]);Choose skip or rob current house

return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));Solve two linear cases excluding first or last house

function robLinear(nums, start, end) {
    if (start > end) return 0;
    if (start === end) return nums[start];
    return Math.max(robLinear(nums, start, end - 1), robLinear(nums, start, end - 2) + nums[end]);
}

function rob(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
    return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}

// Example usage
console.log(rob([2,3,2])); // Output: 3

Line Notes

function robLinear(nums, start, end)Helper for linear subproblem

if (start > end) return 0;Base case: no houses

return Math.max(robLinear(nums, start, end - 1), robLinear(nums, start, end - 2) + nums[end]);Choose skip or rob current house

return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));Solve two linear cases excluding first or last house

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each call branches into two calls, leading to exponential time. Space is linear due to recursion depth.

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

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down Memoization

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

Intuition

Store results of subproblems so that each is computed once, turning exponential recursion into linear time.

Algorithm

1. Create a memo dictionary or array to store results of subproblems.
2. Modify the recursive function to check memo before computing.
3. Compute max loot for two linear cases excluding first or last house.
4. Return the maximum of the two cases.

💡 Memoization transforms the brute force recursion into a dynamic programming solution by caching.

Recurrence:rob(i) = max(rob(i-1), rob(i-2) + nums[i])

</>

Code

def rob_linear(nums, start, end, memo):
    if start > end:
        return 0
    if start == end:
        return nums[start]
    if start in memo:
        return memo[start]
    memo[start] = max(rob_linear(nums, start + 1, end, memo), rob_linear(nums, start + 2, end, memo) + nums[start])
    return memo[start]

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, {}))

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

Line Notes

def rob_linear(nums, start, end, memo):Add memo dict to cache results

if start in memo:Return cached result if available

memo[start] = max(rob_linear(nums, start + 1, end, memo), rob_linear(nums, start + 2, end, memo) + nums[start])Store computed max loot for current start

return max(rob_linear(nums, 0, n - 2, {}), rob_linear(nums, 1, n - 1, {}))Compute two linear cases with memoization

import java.util.HashMap;

public class Solution {
    public int robLinear(int[] nums, int start, int end, HashMap<Integer, Integer> memo) {
        if (start > end) return 0;
        if (start == end) return nums[start];
        if (memo.containsKey(start)) return memo.get(start);
        int result = Math.max(robLinear(nums, start + 1, end, memo), robLinear(nums, start + 2, end, memo) + nums[start]);
        memo.put(start, result);
        return result;
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLinear(nums, 0, n - 2, new HashMap<>()), robLinear(nums, 1, n - 1, new HashMap<>()));
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rob(new int[]{2,3,2})); // Output: 3
    }
}

Line Notes

HashMap<Integer, Integer> memoMemo map caches results for subproblems

if (memo.containsKey(start)) return memo.get(start);Return cached result if present

memo.put(start, result);Store computed result in memo

return Math.max(robLinear(nums, 0, n - 2, new HashMap<>()), robLinear(nums, 1, n - 1, new HashMap<>()));Compute two linear cases with memoization

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

int robLinear(const vector<int>& nums, int start, int end, unordered_map<int,int>& memo) {
    if (start > end) return 0;
    if (start == end) return nums[start];
    if (memo.count(start)) return memo[start];
    memo[start] = max(robLinear(nums, start + 1, end, memo), robLinear(nums, start + 2, end, memo) + nums[start]);
    return memo[start];
}

int rob(const vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    unordered_map<int,int> memo1, memo2;
    return max(robLinear(nums, 0, n - 2, memo1), robLinear(nums, 1, n - 1, memo2));
}

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

Line Notes

unordered_map<int,int>& memoMemo map caches subproblem results

if (memo.count(start)) return memo[start];Return cached result if exists

memo[start] = max(robLinear(nums, start + 1, end, memo), robLinear(nums, start + 2, end, memo) + nums[start]);Store computed max loot

return max(robLinear(nums, 0, n - 2, memo1), robLinear(nums, 1, n - 1, memo2));Compute two linear cases with memoization

function robLinear(nums, start, end, memo) {
    if (start > end) return 0;
    if (start === end) return nums[start];
    if (memo.has(start)) return memo.get(start);
    const result = Math.max(robLinear(nums, start + 1, end, memo), robLinear(nums, start + 2, end, memo) + nums[start]);
    memo.set(start, result);
    return result;
}

function rob(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
    return Math.max(robLinear(nums, 0, n - 2, new Map()), robLinear(nums, 1, n - 1, new Map()));
}

// Example usage
console.log(rob([2,3,2])); // Output: 3

Line Notes

function robLinear(nums, start, end, memo)Memo map caches results

if (memo.has(start)) return memo.get(start);Return cached result if available

memo.set(start, result);Store computed result in memo

return Math.max(robLinear(nums, 0, n - 2, new Map()), robLinear(nums, 1, n - 1, new Map()));Compute two linear cases with memoization

⏱

Complexity

TimeO(n)

SpaceO(n) for memo and recursion stack

Each subproblem is solved once and cached, reducing exponential calls to linear.

💡 For n=10^5, this approach is efficient enough to run within time limits.

Interview Verdict: Accepted

Memoization is a common optimization that turns brute force into a practical solution.

🧠

Bottom-Up Tabulation (Iterative DP)

💡 Tabulation builds the solution iteratively from the base cases up, avoiding recursion and making the process clearer and often faster.

Intuition

Use a dp array where dp[i] stores max loot up to house i, filling it from left to right using the recurrence.

Algorithm

1. Define a helper function to solve the linear house robber problem using dp array.
2. Initialize dp[0] and dp[1] with base cases.
3. Iterate from house 2 to end, filling dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
4. Return dp[n-1] as the max loot for that linear case.
5. Compute two cases excluding first or last house and return max.

💡 Tabulation explicitly stores all subproblem results in an array, making dependencies and order clear.

Recurrence:dp[i] = max(dp[i-1], dp[i-2] + nums[i])

</>

Code

def rob_linear(nums, start, end):
    length = end - start + 1
    if length == 0:
        return 0
    if length == 1:
        return nums[start]
    dp = [0] * length
    dp[0] = nums[start]
    dp[1] = max(nums[start], nums[start + 1])
    for i in range(2, length):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i])
    return dp[-1]

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))

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

Line Notes

dp = [0] * lengthInitialize dp array to store max loot up to each house

dp[0] = nums[start]Base case: max loot at first house is its value

dp[1] = max(nums[start], nums[start + 1])Base case: max loot at second house is max of first two

dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i])Recurrence: rob current or skip

public class Solution {
    public int robLinear(int[] nums, int start, int end) {
        int length = end - start + 1;
        if (length == 0) return 0;
        if (length == 1) return nums[start];
        int[] dp = new int[length];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
        }
        return dp[length - 1];
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rob(new int[]{2,3,2})); // Output: 3
    }
}

Line Notes

int[] dp = new int[length];Create dp array for storing max loot

dp[0] = nums[start];Initialize base case for first house

dp[1] = Math.max(nums[start], nums[start + 1]);Initialize base case for second house

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);Fill dp using recurrence

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

int robLinear(const vector<int>& nums, int start, int end) {
    int length = end - start + 1;
    if (length == 0) return 0;
    if (length == 1) return nums[start];
    vector<int> dp(length);
    dp[0] = nums[start];
    dp[1] = max(nums[start], nums[start + 1]);
    for (int i = 2; i < length; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i]);
    }
    return dp.back();
}

int rob(const vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}

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

Line Notes

vector<int> dp(length);DP array to store max loot

dp[0] = nums[start];Base case initialization

dp[1] = max(nums[start], nums[start + 1]);Second base case

dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i]);Apply recurrence relation

function robLinear(nums, start, end) {
    const length = end - start + 1;
    if (length === 0) return 0;
    if (length === 1) return nums[start];
    const dp = new Array(length).fill(0);
    dp[0] = nums[start];
    dp[1] = Math.max(nums[start], nums[start + 1]);
    for (let i = 2; i < length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
    }
    return dp[length - 1];
}

function rob(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
    return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}

// Example usage
console.log(rob([2,3,2])); // Output: 3

Line Notes

const dp = new Array(length).fill(0);Initialize dp array

dp[0] = nums[start];Base case for first house

dp[1] = Math.max(nums[start], nums[start + 1]);Base case for second house

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);Fill dp using recurrence

⏱

Complexity

TimeO(n)

SpaceO(n)

Iterates once over the houses, storing results in dp array.

💡 For n=10^5, this is efficient and practical.

Interview Verdict: Accepted

This is the standard DP solution for the problem, balancing clarity and efficiency.

🧠

Space Optimized DP

💡 Since dp[i] depends only on dp[i-1] and dp[i-2], we can optimize space by storing only two variables instead of the entire dp array.

Intuition

Keep track of max loot for previous two houses and update iteratively, reducing space from O(n) to O(1).

Algorithm

1. Define a helper function for linear robber problem using two variables prev and curr.
2. Initialize prev and curr with base cases.
3. Iterate through houses, updating curr as max(curr, prev + current house loot).
4. Return curr as max loot for linear case.
5. Compute two cases excluding first or last house and return max.

💡 This approach keeps track of only necessary previous states, saving memory without losing clarity.

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

</>

Code

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))

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

Line Notes

prev, curr = 0, 0Initialize variables to track max loot two steps back and one step back

for i in range(start, end + 1):Iterate over houses in linear range

prev, curr = curr, max(curr, prev + nums[i])Update curr to max of skipping or robbing current house

return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))Compute two linear cases and return max

public class Solution {
    public int robLinear(int[] nums, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; i++) {
            int temp = curr;
            curr = Math.max(curr, prev + nums[i]);
            prev = temp;
        }
        return curr;
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rob(new int[]{2,3,2})); // Output: 3
    }
}

Line Notes

int prev = 0, curr = 0;Track max loot two houses back and previous house

for (int i = start; i <= end; i++) {Iterate over houses in range

curr = Math.max(curr, prev + nums[i]);Update curr with max of robbing or skipping current house

return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));Compute two linear cases and return max

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

int robLinear(const vector<int>& nums, int start, int end) {
    int prev = 0, curr = 0;
    for (int i = start; i <= end; i++) {
        int temp = curr;
        curr = max(curr, prev + nums[i]);
        prev = temp;
    }
    return curr;
}

int rob(const vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}

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

Line Notes

int prev = 0, curr = 0;Track loot two houses back and previous house

for (int i = start; i <= end; i++) {Iterate over houses

curr = max(curr, prev + nums[i]);Update curr with max loot robbing or skipping current house

return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));Compute two linear cases and return max

function robLinear(nums, start, end) {
    let prev = 0, curr = 0;
    for (let i = start; i <= end; i++) {
        let temp = curr;
        curr = Math.max(curr, prev + nums[i]);
        prev = temp;
    }
    return curr;
}

function rob(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
    return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}

// Example usage
console.log(rob([2,3,2])); // Output: 3

Line Notes

let prev = 0, curr = 0;Track loot two houses back and previous house

for (let i = start; i <= end; i++) {Iterate over houses

curr = Math.max(curr, prev + nums[i]);Update curr with max loot robbing or skipping current house

return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));Compute two linear cases and return max

⏱

Complexity

TimeO(n)

SpaceO(1)

Iterates once over houses, storing only two variables for state.

💡 This is the most memory-efficient solution, ideal for large inputs.

Interview Verdict: Accepted

Space optimization is a common final step in DP problems to improve efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Space optimized DP is recommended for interviews due to clarity and efficiency; mention brute force to show understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down Memoization	O(n)	O(n) memo + recursion stack	Possible for large n	Yes	Good for explaining optimization
3. Bottom-Up Tabulation	O(n)	O(n)	No	Yes	Standard solution to code
4. Space Optimized DP	O(n)	O(1)	No	No (without extra tracking)	Best for final optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and circular adjacency.Explain brute force recursion to show understanding of problem structure.Introduce memoization to optimize recursion.Present bottom-up DP for clarity and efficiency.Finally, show space optimization for best performance.

Time Allocation

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

What the Interviewer Tests

Understanding of DP concepts, ability to handle circular constraints, optimization skills, and clean coding.

Common Follow-ups

• What if houses are arranged in a line? → simpler linear DP applies.
• Can you reconstruct which houses were robbed? → yes, by tracking choices during DP.

💡 These follow-ups test your grasp of problem variations and solution extensions.

🔍

Pattern Recognition

When to Use

1) Problem involves maximizing sum with adjacency constraints, 2) Houses arranged in a circle, 3) Need to avoid robbing adjacent houses, 4) Input size requires efficient DP.

Signature Phrases

'houses arranged in a circle''cannot rob adjacent houses''maximum amount of money'

NOT This Pattern When

Problems without adjacency constraints or circular arrangements, e.g., simple maximum subarray sum.

Similar Problems

House Robber I - linear houses without circular constraintPaint House - similar DP with adjacency constraints

Practice

1. You are given a string of digits representing an encoded message where 'A' = 1, 'B' = 2, ..., 'Z' = 26. You need to find the total number of ways to decode the message. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Dynamic programming that builds the count of decodings using previous results

B. Sorting the digits and counting unique permutations

C. Depth-first search without memoization exploring all decoding paths

D. Greedy algorithm that picks the largest valid two-digit number at each step

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all valid decodings, which can overlap and depend on previous computations.

2. Step 2: Identify suitable algorithm

   Dynamic programming efficiently counts ways by reusing previous results, avoiding exponential recomputation unlike naive DFS, and greedy or sorting approaches do not guarantee correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles overlapping subproblems and optimal substructure [OK]

Hint: Count ways using previous results, not greedy or brute force [OK]

Common Mistakes:

• Thinking greedy or sorting solves decoding count correctly

2. Consider the following code snippet implementing the optimal Jump Game solution. What is the value of maxReach after the third iteration (i=2) when input is [2,0,2]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace iterations for input [2,0,2]

   i=0: maxReach = max(0, 0+2) = 2; i=1: maxReach = max(2, 1+0) = 2; i=2: maxReach = max(2, 2+2) = 4

2. Step 2: Identify maxReach after third iteration (i=2)

   After i=2, maxReach is 4, which is the value after the third iteration completes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   maxReach updated to 4 after i=2 [OK]

Hint: Track maxReach updates carefully at each iteration [OK]

Common Mistakes:

• Off-by-one error in iteration count
• Confusing maxReach before vs after update
• Ignoring early return conditions

3. What is the time complexity of the space-optimized DP solution for the Best Time -- 2 Transactions problem with input size n and fixed k=2?

medium

A. O(n^2)

B. O(n * k)

C. O(n)

D. O(k^n)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n-1 times, inner loop runs k times (k=2 fixed). So total iterations ~ n*k.

2. Step 2: Simplify complexity with fixed k

   Since k=2 is constant, O(n*k) simplifies to O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time due to fixed number of transactions [OK]

Hint: Fixed k means linear time, not quadratic [OK]

Common Mistakes:

• Confusing k as variable leading to O(n*k)
• Assuming nested loops always mean O(n^2)

4. Consider the following buggy code snippet for maxProfit. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line with 'if k >= n // 2:' condition

B. Line with 'for j in range(1, k + 1):' loop iterating forwards

C. Line initializing buy array with -float('inf')

D. Line returning sell[k] at the end

Solution

1. Step 1: Identify iteration order in inner loop

   The inner loop iterates forwards from 1 to k, which causes buy[j] to use updated sell[j-1] from the same iteration, corrupting state.

2. Step 2: Correct iteration order

   Iterating backwards from k down to 1 prevents premature overwriting of states, preserving correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Forward iteration overwrites dp states too early [OK]

Hint: Inner loop must run backwards to avoid state overwrite [OK]

Common Mistakes:

• Forgetting to iterate backwards in space optimized DP

5. What is the time and space complexity of the optimal space-optimized dynamic programming solution for the Best Time -- Transaction Fee problem, given n prices?

medium

A. Time: O(n), Space: O(1) by tracking only two states per iteration

B. Time: O(n²), Space: O(n) due to nested loops and DP table

C. Time: O(n), Space: O(n) because of memoization cache or DP array

D. Time: O(n log n), Space: O(1) due to sorting and constant state variables

Solution

1. Step 1: Identify time complexity

   The algorithm iterates once over the prices array, performing constant time operations per element -> O(n).

2. Step 2: Identify space complexity

   Only two variables (cash and hold) are maintained and updated each iteration -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant state variables confirm O(n) time and O(1) space [OK]

Hint: Only two states tracked, no DP table needed [OK]

Common Mistakes:

• Confusing recursion stack space with DP space
• Assuming DP table stored for all days