Longest Increasing Subsequence

🎯

Longest Increasing Subsequence

mediumDPAmazonGoogleMicrosoft

Imagine you are analyzing stock prices over days and want to find the longest period where prices keep increasing steadily.

💡 This problem is a classic example of dynamic programming where beginners often struggle to identify overlapping subproblems and optimal substructure. Understanding the brute force approach helps grasp why DP is needed.

📋

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[10,9,2,5,3,7,101,18]"

Output4

The longest increasing subsequence is [2,3,7,101], so the length is 4.

• Single element array → output is 1
• All elements equal → output is 1
• Strictly decreasing array → output is 1
• Strictly increasing array → output is length of array

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the next bigger element immediately fails because it might miss longer subsequences later. For example, in [3,1,2], greedy picks 3 then stops, but the longest increasing subsequence is [1,2].

DP state:

dp[i] represents the length of the longest increasing subsequence ending exactly at index i.

Recurrence:dp[i] = max(dp[j]) + 1 for all j < i and nums[j] < nums[i], else 1

For each element, look back at all smaller elements before it, take the longest subsequence length among them, and add one to include the current element.

⚠️

Common Mistakes

Not handling the base case correctly in recursion

Leads to infinite recursion or incorrect results

✅ Add base case when index reaches array length

Using '>' instead of '>=' or vice versa in comparisons

Incorrect subsequence length or counting non-strictly increasing sequences

✅ Use strict inequality '>' as problem requires strictly increasing subsequence

Forgetting to memoize both parameters in top-down approach

Memoization ineffective, leading to TLE

✅ Memoize results based on both current index and previous index

Incorrect binary search implementation in optimized approach

Wrong LIS length or runtime errors

✅ Use lower_bound or bisect_left to find correct insertion point

Not initializing dp array with 1 in bottom-up DP

Results in zero or incorrect LIS lengths

✅ Initialize dp array with 1 since each element is LIS of length 1 by itself

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's recursive nature and why naive solutions are inefficient, motivating DP.

Intuition

Try every subsequence by recursively deciding to include or exclude each element, and track the longest increasing subsequence found.

Algorithm

1. Start from the first element and recursively explore subsequences including or excluding it.
2. At each step, keep track of the previous element included to ensure increasing order.
3. Return the maximum length found among all recursive paths.
4. Combine results to find the overall longest increasing subsequence.

💡 The recursion tree grows exponentially because each element has two choices, making it hard to track without memoization.

Recurrence:LIS(i, prev) = max(1 + LIS(i+1, i) if nums[i] > nums[prev], LIS(i+1, prev))

</>

Code

def lengthOfLIS(nums):
    def dfs(i, prev_index):
        if i == len(nums):
            return 0
        taken = 0
        if prev_index == -1 or nums[i] > nums[prev_index]:
            taken = 1 + dfs(i + 1, i)
        not_taken = dfs(i + 1, prev_index)
        return max(taken, not_taken)

    return dfs(0, -1)

# Example usage
if __name__ == '__main__':
    print(lengthOfLIS([10,9,2,5,3,7,101,18]))  # Output: 4

Line Notes

def dfs(i, prev_index):Defines recursive helper to explore subsequences starting at i with prev_index as last included element

if i == len(nums):Base case: reached end of array, no more elements to include

if prev_index == -1 or nums[i] > nums[prev_index]:Check if current element can be included to maintain increasing order

return max(taken, not_taken)Choose the better option between including or skipping current element

public class Solution {
    public int lengthOfLIS(int[] nums) {
        return dfs(nums, 0, -1);
    }

    private int dfs(int[] nums, int i, int prevIndex) {
        if (i == nums.length) return 0;
        int taken = 0;
        if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
            taken = 1 + dfs(nums, i + 1, i);
        }
        int notTaken = dfs(nums, i + 1, prevIndex);
        return Math.max(taken, notTaken);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // 4
    }
}

Line Notes

public int lengthOfLIS(int[] nums)Entry point calling recursive dfs starting at index 0 with no previous element

if (i == nums.length) return 0;Base case: no elements left to process

if (prevIndex == -1 || nums[i] > nums[prevIndex])Check if current element can be included to keep subsequence increasing

return Math.max(taken, notTaken);Return the best choice between including or skipping current element

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

class Solution {
public:
    int dfs(const vector<int>& nums, int i, int prevIndex) {
        if (i == nums.size()) return 0;
        int taken = 0;
        if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
            taken = 1 + dfs(nums, i + 1, i);
        }
        int notTaken = dfs(nums, i + 1, prevIndex);
        return max(taken, notTaken);
    }

    int lengthOfLIS(vector<int>& nums) {
        return dfs(nums, 0, -1);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {10,9,2,5,3,7,101,18};
    cout << sol.lengthOfLIS(nums) << endl; // 4
    return 0;
}

Line Notes

int dfs(const vector<int>& nums, int i, int prevIndex)Recursive helper exploring subsequences starting at i with prevIndex as last included element

if (i == nums.size()) return 0;Base case: no more elements to consider

if (prevIndex == -1 || nums[i] > nums[prevIndex])Include current element if it maintains increasing order

return max(taken, notTaken);Choose the better option between including or skipping current element

function lengthOfLIS(nums) {
    function dfs(i, prevIndex) {
        if (i === nums.length) return 0;
        let taken = 0;
        if (prevIndex === -1 || nums[i] > nums[prevIndex]) {
            taken = 1 + dfs(i + 1, i);
        }
        let notTaken = dfs(i + 1, prevIndex);
        return Math.max(taken, notTaken);
    }
    return dfs(0, -1);
}

// Example usage
console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4

Line Notes

function dfs(i, prevIndex)Recursive helper to explore subsequences starting at i with prevIndex as last included element

if (i === nums.length) return 0;Base case: no more elements to process

if (prevIndex === -1 || nums[i] > nums[prevIndex])Check if current element can be included to maintain increasing order

return Math.max(taken, notTaken);Return the best choice between including or skipping current element

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each element has two choices (include or exclude), leading to exponential growth in calls.

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

Interview Verdict: TLE

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

🧠

Top-Down Memoization

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

Intuition

Store results of LIS computations for each index and previous index pair to reuse them instead of recomputing.

Algorithm

1. Use a recursive function with parameters for current index and previous included index.
2. Check if result for these parameters is already computed in memo table.
3. If yes, return cached result; else compute by including or excluding current element.
4. Store computed result in memo and return it.

💡 Memoization reduces exponential recursion to polynomial by caching results.

Recurrence:dp[i][prevIndex] = max(1 + dp[i+1][i] if nums[i] > nums[prevIndex], dp[i+1][prevIndex])

</>

Code

def lengthOfLIS(nums):
    from functools import lru_cache

    @lru_cache(None)
    def dfs(i, prev_index):
        if i == len(nums):
            return 0
        taken = 0
        if prev_index == -1 or nums[i] > nums[prev_index]:
            taken = 1 + dfs(i + 1, i)
        not_taken = dfs(i + 1, prev_index)
        return max(taken, not_taken)

    return dfs(0, -1)

# Example usage
if __name__ == '__main__':
    print(lengthOfLIS([10,9,2,5,3,7,101,18]))  # Output: 4

Line Notes

@lru_cache(None)Caches results of dfs calls to avoid recomputation

def dfs(i, prev_index):Recursive helper with memoization

if i == len(nums):Base case: no more elements

return max(taken, not_taken)Return best choice using cached results

import java.util.*;

public class Solution {
    private Integer[][] memo;
    private int[] nums;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        memo = new Integer[nums.length][nums.length + 1];
        return dfs(0, -1);
    }

    private int dfs(int i, int prevIndex) {
        if (i == nums.length) return 0;
        int memoIndex = prevIndex + 1;
        if (memo[i][memoIndex] != null) return memo[i][memoIndex];
        int taken = 0;
        if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
            taken = 1 + dfs(i + 1, i);
        }
        int notTaken = dfs(i + 1, prevIndex);
        memo[i][memoIndex] = Math.max(taken, notTaken);
        return memo[i][memoIndex];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // 4
    }
}

Line Notes

private Integer[][] memo;Memo table to cache results for (i, prevIndex) pairs

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

memo[i][memoIndex] = Math.max(taken, notTaken);Store computed result before returning

return memo[i][memoIndex];Return memoized result

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

class Solution {
    vector<vector<int>> memo;
    vector<int> nums;
public:
    int dfs(int i, int prevIndex) {
        if (i == nums.size()) return 0;
        int memoIndex = prevIndex + 1;
        if (memo[i][memoIndex] != -1) return memo[i][memoIndex];
        int taken = 0;
        if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
            taken = 1 + dfs(i + 1, i);
        }
        int notTaken = dfs(i + 1, prevIndex);
        memo[i][memoIndex] = max(taken, notTaken);
        return memo[i][memoIndex];
    }

    int lengthOfLIS(vector<int>& nums) {
        this->nums = nums;
        memo.assign(nums.size(), vector<int>(nums.size() + 1, -1));
        return dfs(0, -1);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {10,9,2,5,3,7,101,18};
    cout << sol.lengthOfLIS(nums) << endl; // 4
    return 0;
}

Line Notes

vector<vector<int>> memo;2D memo table to store results for (i, prevIndex)

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

memo[i][memoIndex] = max(taken, notTaken);Cache computed result before returning

return memo[i][memoIndex];Return memoized value

function lengthOfLIS(nums) {
    const memo = new Map();

    function dfs(i, prevIndex) {
        if (i === nums.length) return 0;
        const key = i + ',' + prevIndex;
        if (memo.has(key)) return memo.get(key);
        let taken = 0;
        if (prevIndex === -1 || nums[i] > nums[prevIndex]) {
            taken = 1 + dfs(i + 1, i);
        }
        let notTaken = dfs(i + 1, prevIndex);
        const res = Math.max(taken, notTaken);
        memo.set(key, res);
        return res;
    }

    return dfs(0, -1);
}

// Example usage
console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4

Line Notes

const memo = new Map();Map to cache results for (i, prevIndex) pairs

const key = i + ',' + prevIndex;Create unique key for memoization

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

memo.set(key, res);Store computed result in memo

⏱

Complexity

TimeO(n^2)

SpaceO(n^2) for memoization and recursion stack

Memoization reduces exponential calls to polynomial by caching results for each (i, prevIndex) pair.

💡 For n=1000, this means about 1 million operations, which is feasible in interviews.

Interview Verdict: Accepted

This approach is efficient enough for moderate input sizes and demonstrates DP memoization well.

🧠

Bottom-Up Tabulation (Classic DP)

💡 This approach iteratively builds the solution from smaller subproblems, making it easier to understand and implement than recursion.

Intuition

For each element, find the length of the longest increasing subsequence ending at that element by checking all previous smaller elements.

Algorithm

1. Initialize a dp array with 1s, since minimum LIS ending at each element is 1.
2. For each element i from left to right, check all elements j before i.
3. If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1).
4. The answer is the maximum value in dp after filling it.

💡 This bottom-up approach avoids recursion and clearly shows how subproblems build up to the final solution.

Recurrence:dp[i] = max(dp[j]) + 1 for all j < i and nums[j] < nums[i], else 1

</>

Code

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0

# Example usage
if __name__ == '__main__':
    print(lengthOfLIS([10,9,2,5,3,7,101,18]))  # Output: 4

Line Notes

dp = [1] * nInitialize dp with 1 since each element alone forms LIS of length 1

for i in range(n):Iterate over each element as potential LIS end

for j in range(i):Check all previous elements to find smaller ones

dp[i] = max(dp[i], dp[j] + 1)Update dp[i] if extending LIS ending at j yields longer subsequence

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxLen = 0;
        for (int len : dp) maxLen = Math.max(maxLen, len);
        return maxLen;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // 4
    }
}

Line Notes

int[] dp = new int[n];Create dp array to store LIS lengths ending at each index

Arrays.fill(dp, 1);Initialize dp with 1 for single-element subsequences

for (int j = 0; j < i; j++)Check all previous elements for smaller values

dp[i] = Math.max(dp[i], dp[j] + 1);Update dp[i] if extending LIS ending at j is beneficial

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

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

int main() {
    Solution sol;
    vector<int> nums = {10,9,2,5,3,7,101,18};
    cout << sol.lengthOfLIS(nums) << endl; // 4
    return 0;
}

Line Notes

vector<int> dp(n, 1);Initialize dp with 1 for each element

for (int j = 0; j < i; j++)Check all previous elements for smaller values

dp[i] = max(dp[i], dp[j] + 1);Update dp[i] if extending LIS ending at j is longer

return *max_element(dp.begin(), dp.end());Return maximum LIS length found

function lengthOfLIS(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp);
}

// Example usage
console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4

Line Notes

const dp = new Array(n).fill(1);Initialize dp array with 1s

for (let j = 0; j < i; j++)Check all previous elements for smaller values

dp[i] = Math.max(dp[i], dp[j] + 1);Update dp[i] if extending LIS ending at j is longer

return Math.max(...dp);Return maximum LIS length found

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops iterate over pairs of elements, and dp array stores LIS lengths.

💡 For n=1000, about 1 million operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the classic DP solution and is often the baseline for LIS problems.

🧠

Optimized DP with Binary Search (Patience Sorting)

💡 This approach uses a clever greedy strategy combined with binary search to achieve O(n log n) time, which is optimal for LIS.

Intuition

Maintain an array that stores the smallest possible tail of increasing subsequences of different lengths. Use binary search to update this array efficiently.

Algorithm

1. Initialize an empty array tails to store smallest tail of increasing subsequences.
2. Iterate over each number in nums.
3. Use binary search to find the position in tails where current number can replace or be appended.
4. If number is larger than all tails, append it; else replace the tail at found position.
5. Length of tails array is the length of the LIS.

💡 This approach cleverly tracks potential subsequences without explicitly storing them, enabling fast updates.

Recurrence:tails array updated by binary searching position to replace or append current element

</>

Code

import bisect

def lengthOfLIS(nums):
    tails = []
    for num in nums:
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num
    return len(tails)

# Example usage
if __name__ == '__main__':
    print(lengthOfLIS([10,9,2,5,3,7,101,18]))  # Output: 4

Line Notes

tails = []Initialize empty list to store smallest tails of subsequences

idx = bisect.bisect_left(tails, num)Find position to insert current number to keep tails sorted

if idx == len(tails):If number is greater than all tails, append it

tails[idx] = numReplace existing tail to maintain minimal tail values

import java.util.*;

public class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int num : nums) {
            int idx = Collections.binarySearch(tails, num);
            if (idx < 0) idx = -(idx + 1);
            if (idx == tails.size()) tails.add(num);
            else tails.set(idx, num);
        }
        return tails.size();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // 4
    }
}

Line Notes

List<Integer> tails = new ArrayList<>();List to store smallest tails of subsequences

int idx = Collections.binarySearch(tails, num);Binary search to find insertion position

if (idx < 0) idx = -(idx + 1);Convert negative insertion point to index

tails.set(idx, num);Replace tail to maintain minimal values

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

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int num : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), num);
            if (it == tails.end()) tails.push_back(num);
            else *it = num;
        }
        return tails.size();
    }
};

int main() {
    Solution sol;
    vector<int> nums = {10,9,2,5,3,7,101,18};
    cout << sol.lengthOfLIS(nums) << endl; // 4
    return 0;
}

Line Notes

vector<int> tails;Vector to store smallest tails of subsequences

auto it = lower_bound(tails.begin(), tails.end(), num);Binary search to find position to replace or append

if (it == tails.end()) tails.push_back(num);Append if num is greater than all tails

*it = num;Replace tail to keep minimal values

function lengthOfLIS(nums) {
    const tails = [];
    for (const num of nums) {
        let left = 0, right = tails.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) left = mid + 1;
            else right = mid;
        }
        if (right === tails.length) tails.push(num);
        else tails[right] = num;
    }
    return tails.length;
}

// Example usage
console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4

Line Notes

const tails = [];Array to store smallest tails of subsequences

while (left < right)Binary search to find correct position for current number

if (right === tails.length) tails.push(num);Append if number is larger than all tails

else tails[right] = num;Replace tail to maintain minimal values

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Each element is processed once with a binary search on tails array.

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

Interview Verdict: Accepted

This is the optimal solution for LIS and is highly recommended for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, coding the bottom-up DP or the binary search optimized approach is best; brute force is only for explanation.

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^2)	O(n^2)	Possible for large n	Yes	Good for explaining DP optimization
3. Bottom-Up Tabulation	O(n^2)	O(n)	No	Yes	Standard DP solution to code
4. Binary Search Optimization	O(n log n)	O(n)	No	No (without extra work)	Optimal solution, mention or code if confident

💼

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 the problem and constraints with the interviewer.Explain the brute force recursive approach to show understanding of the problem structure.Introduce memoization to optimize overlapping subproblems.Present the bottom-up DP solution as a standard approach.If time permits, discuss the binary search optimization for best performance.Write clean code and test with sample inputs.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion and DP, ability to optimize solutions, knowledge of binary search, and clear communication.

Common Follow-ups

• How to reconstruct the actual LIS sequence? → Use parent pointers or backtracking from dp array.
• Can you optimize space complexity? → Bottom-up DP already uses O(n) space; binary search approach uses O(n).

💡 These follow-ups test deeper understanding and ability to extend solutions beyond just length calculation.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest increasing subsequence or similar. 2) Input is a sequence or array. 3) Need to find length or count of subsequences. 4) Overlapping subproblems and optimal substructure are present.

Signature Phrases

longest increasing subsequencestrictly increasingsubsequence length

NOT This Pattern When

Longest Increasing Subarray - requires contiguous elements, solved differently

Similar Problems

Longest Common Subsequence - similar DP structure but compares two sequencesMaximum Sum Increasing Subsequence - variation maximizing sum instead of length

Practice

1. Given the following code for the House Robber III problem, what is the final returned value when called with the tree below? Tree structure: ``` 3 / \ 2 3 \ \ 3 1 ```

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[0] + right[0]
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob(root))

easy

A. 6

B. 9

C. 8

D. 7

Solution

1. Step 1: Trace dfs on leaf nodes

   Leaf nodes 3 and 1 return (0,3) and (0,1) respectively.

2. Step 2: Compute dfs for internal nodes

   Node 2: rob_node = 2 + 0 + 0 = 2, not_rob_node = max(0,3) + 0 = 3; returns (3,2). Node 3 (right child): rob_node = 3 + 0 + 0 = 3, not_rob_node = 0 + max(0,1) = 1; returns (1,3). Root 3: rob_node = 3 + 3 + 1 = 7, not_rob_node = max(3,2) + max(1,3) = 3 + 3 = 6.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Maximum is max(6,7) = 7 [OK]

Hint: Trace bottom-up dp states carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Confusing rob and not_rob states at nodes

2. Consider the following buggy code for the House Robber III problem. Which line contains the subtle bug that causes incorrect results on some inputs?

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[1] + right[1]  # Bug here
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

medium

A. Line returning max of dfs(root) instead of sum

B. Line computing rob_node sums children rob values instead of not_rob values

C. Line returning (not_rob_node, rob_node) tuple instead of single value

D. Line checking if node is null and returning (0,0)

Solution

1. Step 1: Understand rob_node calculation

   When robbing current node, children cannot be robbed, so we must add left[0] and right[0] (not_rob values).

2. Step 2: Identify bug

   The code incorrectly adds left[1] and right[1] (rob values), causing double counting and invalid solutions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct rob_node uses not_rob children sums [OK]

Hint: Robbing node requires adding children's not_rob values [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple

3. Examine the following buggy code snippet for shortest path visiting all nodes. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line setting base cases: dp[i][1 << i] = 0

B. Line updating next_mask: next_mask = mask ^ (1 << v)

C. Line with dp initialization: dp = [[float('inf')] * (1 << n) for _ in range(n)]

D. Line updating dp[v][next_mask]: dp[v][next_mask] = dp[u][mask] + 1

Solution

1. Step 1: Identify how visited nodes are tracked

   Visited nodes are represented by a bitmask. To add a visited node, bitwise OR (|) must be used.

2. Step 2: Spot the incorrect bitmask operation

   The code uses XOR (^) instead of OR (|) to update next_mask, which can incorrectly unset bits and cause wrong states or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using XOR breaks the visited set semantics [OK]

Hint: Visited mask update must use OR, not XOR [OK]

Common Mistakes:

• Using XOR instead of OR for mask update
• Forgetting to initialize dp base cases
• Not checking dp[u][mask] == inf before continuing

4. Suppose the problem is modified so that you can revisit cells multiple times (cycles allowed) and the path must be strictly increasing. Which approach correctly handles this variant without infinite loops?

hard

A. Use DFS with memoization and cycle detection to avoid infinite loops

B. Use topological sort based DP after detecting and removing cycles

C. Use BFS ignoring value order to find longest path

D. Use DFS without memoization to explore all paths

Solution

1. Step 1: Understand cycle implications

   Allowing revisits with strict increasing values can create cycles if not carefully handled, risking infinite loops.

2. Step 2: Identify safe approach

   DFS with memoization plus cycle detection prevents infinite recursion and correctly computes longest paths even with cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization + cycle detection ensures correctness and termination [OK]

Hint: Cycle detection needed when revisits allowed [OK]

Common Mistakes:

• Using naive DFS causing infinite loops
• Ignoring cycles in topological sort
• Using BFS without value order

5. Suppose the Travelling Salesman Problem is modified so that cities can be visited multiple times (revisits allowed). Which of the following changes to the bottom-up bitmask DP approach correctly adapts to this variant?

hard

A. Remove the bitmask representing visited cities and use simple DP over current city and steps taken

B. Keep the bitmask DP as is, since revisits do not affect the visited set representation

C. Use a shortest path algorithm like Floyd-Warshall instead of DP

D. Modify the DP to track the count of visits per city in the state

Solution

1. Step 1: Understand revisits break bitmask usage

   Bitmask DP relies on each city visited exactly once; revisits mean visited set is no longer sufficient to represent state.

2. Step 2: Adapt DP state to allow revisits

   Removing bitmask and using DP over current city and number of steps (or path length) allows revisits, as visited set is not tracked.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask DP is invalid if cities can be revisited [OK]

Hint: Bitmask DP encodes unique visits; revisits require different state [OK]

Common Mistakes:

• Assuming bitmask DP works unchanged with revisits