Decode Ways

🎯

Decode Ways

mediumDPAmazonFacebookGoogle

Imagine receiving a secret message encoded as digits, where each number maps to a letter. How many ways can you decode it back to readable text?

💡 This problem is a classic example of counting the number of ways to decode a string of digits. Beginners often struggle because the problem looks like a string problem but requires dynamic programming to efficiently count valid decodings without enumerating all possibilities.

📋

Problem Statement

Given a string s containing only digits, return the number of ways to decode it. The mapping is 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. A decoding is valid if each digit or pair of digits maps to a letter. Return 0 if no valid decoding exists.

1 ≤ s.length ≤ 10^5s contains only digits '0'–9'

💡

Example

Input"12"

Output2

The string '12' can be decoded as 'AB' (1 2) or 'L' (12).

Input"226"

Output3

'226' can be decoded as 'BZ' (2 26), 'VF' (22 6), or 'BBF' (2 2 6).

Input"0"

Output0

No valid decoding starts with '0'.

Input"06"

Output0

Leading zero invalidates decoding.

• Single digit '0' → 0 ways
• String with multiple zeros like '100' → 1 way (only '10' valid, '0' alone invalid)
• Long string of '1's like '111111' → multiple ways (exponential in brute force)
• String with invalid pairs like '30' → 0 ways

🔁

Why DP?

Why greedy fails:

A greedy approach might pick the largest valid two-digit number at each step, but this fails. For example, '111' greedy picks '11' then '1' for 2 ways, but actually there are 3 ways: '1 1 1', '11 1', '1 11'.

DP state:

dp[i] = number of ways to decode the substring s[0..i-1] (first i characters).

Recurrence:dp[i] = (if s[i-1] valid) dp[i-1] + (if s[i-2..i-1] valid) dp[i-2]

The ways to decode up to i include ways decoding up to i-1 if the last single digit is valid, plus ways decoding up to i-2 if the last two digits form a valid letter.

⚠️

Common Mistakes

Treating '0' as valid single digit

Returns incorrect counts or crashes

✅ Explicitly check and return 0 if current digit is '0' unless part of valid two-digit number

Not checking two-digit number validity properly

Counts invalid decodings like '30' or '00'

✅ Check two-digit number is between 10 and 26 inclusive

Forgetting base case dp[0] = 1

DP array remains zero leading to zero final count

✅ Initialize dp[0] = 1 to represent empty string decoding

Using recursion without memoization on large inputs

Time limit exceeded or stack overflow

✅ Add memoization or switch to bottom-up DP

Incorrect indexing when slicing substrings

Runtime errors or wrong counts

✅ Carefully use zero-based indexing and substring ranges

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated computations.

Intuition

Try decoding one digit or two digits at a time recursively, summing all valid decoding ways.

Algorithm

1. Start from index 0 of the string.
2. If current digit is valid (not '0'), recurse by moving one step forward.
3. If next two digits form a valid number between 10 and 26, recurse by moving two steps forward.
4. Sum the results of both recursions to get total ways.

💡 The recursion tree grows exponentially because it explores all valid splits without remembering results.

Recurrence:dp[i] = (if s[i] valid) dp[i+1] + (if s[i..i+1] valid) dp[i+2]

</>

Code

def numDecodings(s: str) -> int:
    def dfs(i):
        if i == len(s):
            return 1
        if s[i] == '0':
            return 0
        res = dfs(i+1)
        if i+1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
            res += dfs(i+2)
        return res
    return dfs(0)

# Example usage
if __name__ == '__main__':
    print(numDecodings('226'))  # Output: 3

Line Notes

def dfs(i):Defines recursive helper to count ways starting at index i

if i == len(s):Base case: reached end means one valid decoding

if s[i] == '0':No decoding starts with '0', so return 0

res = dfs(i+1)Count ways decoding one digit

if i+1 < len(s) and 10 <= int(s[i:i+2]) <= 26:Check if two-digit decode is valid

res += dfs(i+2)Add ways decoding two digits

return dfs(0)Start recursion from index 0

public class Solution {
    public int numDecodings(String s) {
        return dfs(s, 0);
    }
    private int dfs(String s, int i) {
        if (i == s.length()) return 1;
        if (s.charAt(i) == '0') return 0;
        int res = dfs(s, i + 1);
        if (i + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(i, i + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                res += dfs(s, i + 2);
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDecodings("226")); // 3
    }
}

Line Notes

public int numDecodings(String s)Entry point calling recursive helper

if (i == s.length()) return 1;Base case: full string decoded

if (s.charAt(i) == '0') return 0;Invalid decode if starts with zero

int res = dfs(s, i + 1);Count ways decoding one digit

if (i + 1 < s.length())Check if two-digit decode possible

if (twoDigit >= 10 && twoDigit <= 26)Validate two-digit number

res += dfs(s, i + 2);Add ways decoding two digits

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

class Solution {
public:
    int dfs(const string& s, int i) {
        if (i == s.size()) return 1;
        if (s[i] == '0') return 0;
        int res = dfs(s, i + 1);
        if (i + 1 < s.size()) {
            int twoDigit = stoi(s.substr(i, 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                res += dfs(s, i + 2);
            }
        }
        return res;
    }
    int numDecodings(string s) {
        return dfs(s, 0);
    }
};

int main() {
    Solution sol;
    cout << sol.numDecodings("226") << endl; // 3
    return 0;
}

Line Notes

int dfs(const string& s, int i)Recursive helper counting ways from index i

if (i == s.size()) return 1;Base case: full decode reached

if (s[i] == '0') return 0;No decode starts with zero

int res = dfs(s, i + 1);Count ways decoding one digit

if (i + 1 < s.size())Check if two-digit decode possible

int twoDigit = stoi(s.substr(i, 2));Extract two-digit number

if (twoDigit >= 10 && twoDigit <= 26)Validate two-digit number

res += dfs(s, i + 2);Add ways decoding two digits

function numDecodings(s) {
    function dfs(i) {
        if (i === s.length) return 1;
        if (s[i] === '0') return 0;
        let res = dfs(i + 1);
        if (i + 1 < s.length && +s.substring(i, i + 2) >= 10 && +s.substring(i, i + 2) <= 26) {
            res += dfs(i + 2);
        }
        return res;
    }
    return dfs(0);
}

console.log(numDecodings('226')); // 3

Line Notes

function dfs(i)Recursive helper counting ways from index i

if (i === s.length) return 1;Base case: full decode reached

if (s[i] === '0') return 0;No decode starts with zero

let res = dfs(i + 1);Count ways decoding one digit

if (i + 1 < s.length && +s.substring(i, i + 2) >= 10 && +s.substring(i, i + 2) <= 26)Check two-digit validity

res += dfs(i + 2);Add ways decoding two digits

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each index can branch into two recursive calls, leading to exponential time.

💡 For n=20, this means over a million calls, which is too slow for large inputs.

Interview Verdict: TLE

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

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing results for the same substring, drastically improving efficiency while keeping the recursive structure.

Intuition

Store results of recursive calls in a cache so repeated calls return instantly.

Algorithm

1. Initialize a memo dictionary to store results for each index.
2. Recursively compute ways from index i, returning cached result if available.
3. Check single and double digit validity as before.
4. Sum and cache the results before returning.

💡 Memoization turns exponential recursion into linear by pruning repeated calls.

Recurrence:dp[i] = (if s[i] valid) dp[i+1] + (if s[i..i+1] valid) dp[i+2]

</>

Code

def numDecodings(s: str) -> int:
    memo = {}
    def dfs(i):
        if i in memo:
            return memo[i]
        if i == len(s):
            return 1
        if s[i] == '0':
            return 0
        res = dfs(i+1)
        if i+1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
            res += dfs(i+2)
        memo[i] = res
        return res
    return dfs(0)

# Example usage
if __name__ == '__main__':
    print(numDecodings('226'))  # Output: 3

Line Notes

memo = {}Cache to store results for indices

if i in memo:Return cached result if available

memo[i] = resStore computed result before returning

return dfs(0)Start recursion from index 0

import java.util.HashMap;
public class Solution {
    private HashMap<Integer, Integer> memo = new HashMap<>();
    public int numDecodings(String s) {
        return dfs(s, 0);
    }
    private int dfs(String s, int i) {
        if (memo.containsKey(i)) return memo.get(i);
        if (i == s.length()) return 1;
        if (s.charAt(i) == '0') return 0;
        int res = dfs(s, i + 1);
        if (i + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(i, i + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                res += dfs(s, i + 2);
            }
        }
        memo.put(i, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDecodings("226")); // 3
    }
}

Line Notes

private HashMap<Integer, Integer> memoCache for memoization

if (memo.containsKey(i))Return cached result if present

memo.put(i, res)Store computed result

return dfs(s, 0)Start recursion from index 0

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<int, int> memo;
public:
    int dfs(const string& s, int i) {
        if (memo.count(i)) return memo[i];
        if (i == s.size()) return 1;
        if (s[i] == '0') return 0;
        int res = dfs(s, i + 1);
        if (i + 1 < s.size()) {
            int twoDigit = stoi(s.substr(i, 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                res += dfs(s, i + 2);
            }
        }
        memo[i] = res;
        return res;
    }
    int numDecodings(string s) {
        return dfs(s, 0);
    }
};

int main() {
    Solution sol;
    cout << sol.numDecodings("226") << endl; // 3
    return 0;
}

Line Notes

unordered_map<int, int> memoCache for memoization

if (memo.count(i)) return memo[i];Return cached result if available

memo[i] = res;Store computed result

return dfs(s, 0);Start recursion from index 0

function numDecodings(s) {
    const memo = new Map();
    function dfs(i) {
        if (memo.has(i)) return memo.get(i);
        if (i === s.length) return 1;
        if (s[i] === '0') return 0;
        let res = dfs(i + 1);
        if (i + 1 < s.length && +s.substring(i, i + 2) >= 10 && +s.substring(i, i + 2) <= 26) {
            res += dfs(i + 2);
        }
        memo.set(i, res);
        return res;
    }
    return dfs(0);
}

console.log(numDecodings('226')); // 3

Line Notes

const memo = new Map();Cache for memoization

if (memo.has(i)) return memo.get(i);Return cached result if present

memo.set(i, res);Store computed result

return dfs(0);Start recursion from index 0

⏱

Complexity

TimeO(n)

SpaceO(n) for memo and recursion stack

Each index computed once, linear time overall.

💡 For n=20, only 20 calls happen instead of millions.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for large inputs.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from the base case, avoiding recursion and making the flow easier to understand and debug.

Intuition

Use a dp array where dp[i] stores ways to decode substring s[:i], fill it from left to right.

Algorithm

1. Initialize dp array of size n+1 with dp[0] = 1 (empty string).
2. Iterate i from 1 to n:
3. Check if single digit s[i-1] is valid, add dp[i-1] to dp[i].
4. Check if two digits s[i-2..i-1] valid, add dp[i-2] to dp[i].
5. Return dp[n] as the total ways.

💡 This approach explicitly shows how smaller subproblems combine to solve bigger ones.

Recurrence:dp[i] = (if s[i-1] valid) dp[i-1] + (if s[i-2..i-1] valid) dp[i-2]

</>

Code

def numDecodings(s: str) -> int:
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        if i > 1 and 10 <= int(s[i-2:i]) <= 26:
            dp[i] += dp[i-2]
    return dp[n]

# Example usage
if __name__ == '__main__':
    print(numDecodings('226'))  # Output: 3

Line Notes

dp = [0] * (n + 1)Create dp array to store counts for substrings

dp[0] = 1Base case: empty string has one way to decode

if s[i-1] != '0':Single digit valid check

dp[i] += dp[i-1]Add ways from previous substring

if i > 1 and 10 <= int(s[i-2:i]) <= 26:Two-digit valid check

dp[i] += dp[i-2]Add ways from substring excluding last two digits

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1) {
                int twoDigit = Integer.parseInt(s.substring(i - 2, i));
                if (twoDigit >= 10 && twoDigit <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDecodings("226")); // 3
    }
}

Line Notes

int[] dp = new int[n + 1];DP array to store counts

dp[0] = 1;Base case: empty string decode count

if (s.charAt(i - 1) != '0')Check single digit validity

dp[i] += dp[i - 1];Add ways from previous index

if (i > 1)Check two-digit substring validity

dp[i] += dp[i - 2];Add ways from two indices before

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

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1) {
                int twoDigit = stoi(s.substr(i - 2, 2));
                if (twoDigit >= 10 && twoDigit <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[n];
    }
};

int main() {
    Solution sol;
    cout << sol.numDecodings("226") << endl; // 3
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);DP array initialization

dp[0] = 1;Base case for empty string

if (s[i - 1] != '0')Check single digit validity

dp[i] += dp[i - 1];Add ways from previous substring

if (i > 1)Check two-digit substring validity

dp[i] += dp[i - 2];Add ways from two steps before

function numDecodings(s) {
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= n; i++) {
        if (s[i - 1] !== '0') {
            dp[i] += dp[i - 1];
        }
        if (i > 1) {
            const twoDigit = +s.substring(i - 2, i);
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[n];
}

console.log(numDecodings('226')); // 3

Line Notes

const dp = new Array(n + 1).fill(0);Initialize dp array with zeros

dp[0] = 1;Base case: empty string decode count

if (s[i - 1] !== '0')Check single digit validity

dp[i] += dp[i - 1];Add ways from previous index

if (i > 1)Check two-digit substring validity

dp[i] += dp[i - 2];Add ways from two indices before

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through string with constant time checks per index.

💡 For n=20, only 20 iterations with simple checks.

Interview Verdict: Accepted

Bottom-up DP is efficient and preferred for iterative clarity.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i] depends only on dp[i-1] and dp[i-2], we can reduce space from O(n) to O(1) by storing only two previous states.

Intuition

Keep track of only the last two counts instead of the whole dp array.

Algorithm

1. Initialize two variables to represent dp[0] and dp[1].
2. Iterate through the string from index 1 to n.
3. Update current ways based on single and double digit validity using previous two variables.
4. Shift variables forward to represent dp[i-1] and dp[i] for next iteration.
5. Return the last computed value as the total ways.

💡 This approach maintains the same logic as tabulation but uses variables instead of an array.

Recurrence:dp[i] = (if s[i-1] valid) dp[i-1] + (if s[i-2..i-1] valid) dp[i-2]

</>

Code

def numDecodings(s: str) -> int:
    n = len(s)
    if not s or s[0] == '0':
        return 0
    prev2, prev1 = 1, 1
    for i in range(1, n):
        curr = 0
        if s[i] != '0':
            curr += prev1
        two_digit = int(s[i-1:i+1])
        if 10 <= two_digit <= 26:
            curr += prev2
        prev2, prev1 = prev1, curr
    return prev1

# Example usage
if __name__ == '__main__':
    print(numDecodings('226'))  # Output: 3

Line Notes

if not s or s[0] == '0':Early return if string empty or starts with zero

prev2, prev1 = 1, 1Initialize dp[-2] and dp[-1] equivalent

for i in range(1, n):Iterate through string indices

curr = 0Current count initialization

if s[i] != '0':Check single digit validity

curr += prev1Add ways from previous index

if 10 <= two_digit <= 26:Check two-digit validity

curr += prev2Add ways from two indices before

prev2, prev1 = prev1, currShift variables for next iteration

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
        int prev2 = 1, prev1 = 1;
        for (int i = 1; i < s.length(); i++) {
            int curr = 0;
            if (s.charAt(i) != '0') curr += prev1;
            int twoDigit = Integer.parseInt(s.substring(i - 1, i + 1));
            if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDecodings("226")); // 3
    }
}

Line Notes

if (s == null || s.length() == 0 || s.charAt(0) == '0')Early return for invalid input

int prev2 = 1, prev1 = 1;Initialize counts for dp[-2] and dp[-1]

for (int i = 1; i < s.length(); i++)Iterate through string

if (s.charAt(i) != '0') curr += prev1;Add ways from previous index if single digit valid

if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;Add ways from two indices before if valid

prev2 = prev1; prev1 = curr;Update previous counts for next iteration

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

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int prev2 = 1, prev1 = 1;
        for (int i = 1; i < s.size(); i++) {
            int curr = 0;
            if (s[i] != '0') curr += prev1;
            int twoDigit = stoi(s.substr(i - 1, 2));
            if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

int main() {
    Solution sol;
    cout << sol.numDecodings("226") << endl; // 3
    return 0;
}

Line Notes

if (s.empty() || s[0] == '0') return 0;Early return for invalid input

int prev2 = 1, prev1 = 1;Initialize counts for dp[-2] and dp[-1]

for (int i = 1; i < s.size(); i++)Iterate through string

if (s[i] != '0') curr += prev1;Add ways from previous index if single digit valid

if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;Add ways from two indices before if valid

prev2 = prev1; prev1 = curr;Update previous counts for next iteration

function numDecodings(s) {
    if (!s || s[0] === '0') return 0;
    let prev2 = 1, prev1 = 1;
    for (let i = 1; i < s.length; i++) {
        let curr = 0;
        if (s[i] !== '0') curr += prev1;
        const twoDigit = +s.substring(i - 1, i + 1);
        if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

console.log(numDecodings('226')); // 3

Line Notes

if (!s || s[0] === '0') return 0;Early return for invalid input

let prev2 = 1, prev1 = 1;Initialize counts for dp[-2] and dp[-1]

for (let i = 1; i < s.length; i++)Iterate through string

if (s[i] !== '0') curr += prev1;Add ways from previous index if single digit valid

if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;Add ways from two indices before if valid

prev2 = prev1; prev1 = curr;Update previous counts for next iteration

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass with constant space variables.

💡 For n=20, only 20 iterations and 3 variables used.

Interview Verdict: Accepted

This is the most optimal approach in terms of space and time for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding bottom-up DP or space optimized DP is usually best. Brute force is good to explain but not to code fully.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down DP with Memoization	O(n)	O(n) memo + recursion stack	Possible but less likely	Yes with extra tracking	Good to code if comfortable with recursion
3. Bottom-Up DP (Tabulation)	O(n)	O(n)	No	Yes with extra arrays	Preferred approach to code
4. Space Optimized Bottom-Up DP	O(n)	O(1)	No	No (without extra work)	Best for optimal solution

💼

Interview Strategy

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

How to Present

Step 1: Clarify input constraints and problem statement.Step 2: Explain brute force recursive approach and its inefficiency.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up DP for iterative clarity.Step 5: Show space optimization for best performance.Step 6: Test with edge cases and explain complexity.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion, memoization, DP state definition, handling edge cases like zeros, and ability to optimize space/time.

Common Follow-ups

• What if the mapping changes to include '0' as a valid letter? → Adjust validity checks accordingly.
• How to reconstruct one valid decoding? → Use backtracking or store choices during DP.

💡 Follow-ups test flexibility in adapting the solution and extending it beyond counting.

🔍

Pattern Recognition

When to Use

1) Problem asks for number of ways to decode or count sequences; 2) Input is a string or array; 3) Validity depends on single or pairs of elements; 4) Overlapping subproblems with optimal substructure.

Signature Phrases

number of ways to decodemapping from digits to letters

NOT This Pattern When

Problems that require greedy or backtracking without overlapping subproblems.

Similar Problems

Climbing Stairs - counting ways with 1 or 2 stepsUnique Paths - counting paths with constraintsWord Break - segmenting strings with dictionary

Practice

1. You are given an array of stock prices where you can complete at most two transactions (buy-sell pairs). Which algorithmic approach guarantees finding the maximum profit efficiently?

easy

A. Dynamic programming with state machine tracking transactions and holding states

B. Greedy approach that picks local minima and maxima twice

C. Brute force checking all pairs of buy and sell days twice

D. Divide and conquer splitting the array into two halves and combining results

Solution

1. Step 1: Understand problem constraints

   At most two transactions means we must track states for 0, 1, or 2 completed transactions and whether we hold stock or not.

2. Step 2: Identify suitable algorithm

   Greedy and divide-and-conquer fail to consider overlapping subproblems and state transitions correctly. Brute force is correct but inefficient. DP with state machines efficiently tracks profits per transaction count and holding state.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP with states is standard for multi-transaction stock problems [OK]

Hint: Track transactions and holding states with DP [OK]

Common Mistakes:

• Assuming greedy picks always yield global optimum
• Using brute force without pruning

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

3. What is the time complexity of the optimal greedy solution for the Jump Game II problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because it checks all possible jumps from each position

B. O(n) because it scans the array once, updating furthest reachable index and jumps

C. O(n log n) due to sorting or priority queue operations

D. O(2^n) because it explores all jump paths recursively

Solution

1. Step 1: Identify loop structure

   The greedy solution iterates through the array once (n-1 iterations), updating furthest reachable index and jumps.

2. Step 2: Understand why complexity is O(n)

   Each element is processed once, no nested loops or recursion, so time complexity is linear O(n). Candidates often mistake it for O(n^2) because brute force or DP solutions check all jumps from each position.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant work per iteration confirms O(n) [OK]

Hint: Greedy scans array once, no nested loops [OK]

Common Mistakes:

• Confusing greedy with brute force or DP complexity
• Assuming nested loops due to jump ranges
• Ignoring that jumps increment only at range ends

4. Consider the following buggy code for minimum cost climbing stairs. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line 4: Loop range starting at 2

B. Line 7: Returning prev1 instead of min(prev1, prev2)

C. Line 6: Updating prev2 and prev1

D. Line 3: Initialization of prev2 and prev1

Solution

1. Step 1: Understand final return logic

   The top can be reached from either last step or second last step, so minimum of prev1 and prev2 must be returned.

2. Step 2: Identify incorrect return

   Returning only prev1 ignores the possibility that prev2 might be cheaper, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return min(prev1, prev2) to cover both possible last steps [OK]

Hint: Return min of last two costs, not just last [OK]

Common Mistakes:

• Forgetting min at return
• Misinitializing base cases
• Incorrect loop boundaries

5. If the Jump Game II problem is modified so that you can reuse positions multiple times (i.e., cycles allowed), which approach correctly finds the minimum jumps without infinite loops?

hard

A. Use a breadth-first search (BFS) on the graph of positions to find shortest path

B. Use the original greedy approach as is, since it always finds minimum jumps

C. Use a brute force recursion exploring all paths without memoization

D. Use bottom-up DP ignoring cycles, assuming no repeated states

Solution

1. Step 1: Understand the impact of allowing cycles

   Allowing reuse of positions means cycles can occur, so greedy or naive DP may loop infinitely or give wrong answers.

2. Step 2: Identify correct approach

   BFS on the graph of positions treats each index as a node and edges as jumps, finding shortest path (minimum jumps) while avoiding infinite loops by tracking visited nodes.

3. Step 3: Why other options fail

   Greedy assumes no cycles and can fail. Brute force recursion without memoization causes infinite recursion. Bottom-up DP ignoring cycles may not terminate or produce incorrect results.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   BFS finds shortest path in graphs with cycles safely [OK]

Hint: Cycles require BFS with visited tracking to avoid infinite loops [OK]

Common Mistakes:

• Applying greedy blindly despite cycles
• Ignoring infinite recursion in brute force
• Assuming DP works without cycle checks