Number of Longest Increasing Subsequences

🎯

Number of Longest Increasing Subsequences

mediumDPGoogleAmazon

Imagine you are analyzing stock prices over days and want to find not just the longest increasing trend but also how many such longest trends exist.

💡 This problem extends the classic Longest Increasing Subsequence (LIS) by requiring counting all LIS, which adds complexity. Beginners often struggle because they must track both length and count simultaneously, which is not intuitive at first.

📋

Problem Statement

Given an integer array nums, return the number of longest strictly increasing subsequences. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

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

💡

Example

Input"[1,3,5,4,7]"

Output2

The longest increasing subsequence length is 4. There are two such subsequences: [1,3,4,7] and [1,3,5,7].

Input"[2,2,2,2,2]"

Output5

All elements are equal, so the longest increasing subsequence length is 1, and there are 5 such subsequences (each element alone).

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

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the first increasing subsequence found fails because it ignores multiple subsequences of the same maximum length. For example, in [1,3,5,4,7], greedy might pick [1,3,5,7] and miss [1,3,4,7].

DP state:

dp[i] stores the length of the longest increasing subsequence ending at index i; count[i] stores how many such longest subsequences end at i.

Recurrence:For each i, dp[i] = max(dp[j]) + 1 for all j < i where nums[j] < nums[i]; count[i] = sum of count[j] for all such j where dp[j] is max.

For each element, find the longest subsequence length among smaller elements before it, then add one. The count sums how many sequences achieve that length.

⚠️

Common Mistakes

Not initializing count array with 1

Counts remain zero leading to incorrect final count

✅ Initialize count array with 1 since each element alone forms an LIS of length 1

Updating count[i] incorrectly when dp[j] + 1 == dp[i]

Undercounts number of LIS by missing multiple paths

✅ Add count[j] to count[i] when dp[j] + 1 equals dp[i]

Using greedy approach to pick one LIS

Fails to count all LIS, returns wrong answer

✅ Use DP to track lengths and counts for all subsequences

Not handling duplicates correctly in optimized approach

Fenwick tree queries may double count or miss counts

✅ Use coordinate compression and careful Fenwick tree updates

Off-by-one errors in Fenwick tree indexing

Incorrect queries or updates leading to wrong results

✅ Use 1-based indexing consistently in Fenwick tree

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's structure by exploring all subsequences, but it is inefficient and impractical for large inputs.

Intuition

Try every subsequence and track the longest increasing ones, counting how many have the maximum length.

Algorithm

1. Generate all subsequences recursively.
2. For each subsequence, check if it is strictly increasing.
3. Track the length of the longest increasing subsequence found so far.
4. Count how many subsequences have this maximum length.

💡 The recursion tree grows exponentially, making it hard to follow and inefficient, but it lays the foundation for DP.

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

</>

Code

def findNumberOfLIS(nums):
    n = len(nums)
    max_len = 0
    count = 0

    def dfs(index, prev_index, length):
        nonlocal max_len, count
        if index == n:
            if length > max_len:
                max_len = length
                count = 1
            elif length == max_len:
                count += 1
            return
        # Skip current
        dfs(index + 1, prev_index, length)
        # Take current if increasing
        if prev_index == -1 or nums[index] > nums[prev_index]:
            dfs(index + 1, index, length + 1)

    dfs(0, -1, 0)
    return count

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

Line Notes

def findNumberOfLIS(nums):Defines main function to solve problem

nonlocal max_len, countAllows modification of outer variables inside dfs

if index == n:Base case: reached end of array

dfs(index + 1, prev_index, length)Explore subsequence without current element

if prev_index == -1 or nums[index] > nums[prev_index]:Include current element if increasing

import java.util.*;
public class NumberOfLIS {
    static int maxLen = 0, count = 0;
    public static void dfs(int[] nums, int index, int prevIndex, int length) {
        if (index == nums.length) {
            if (length > maxLen) {
                maxLen = length;
                count = 1;
            } else if (length == maxLen) {
                count++;
            }
            return;
        }
        // Skip current
        dfs(nums, index + 1, prevIndex, length);
        // Take current if increasing
        if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
            dfs(nums, index + 1, index, length + 1);
        }
    }
    public static int findNumberOfLIS(int[] nums) {
        maxLen = 0; count = 0;
        dfs(nums, 0, -1, 0);
        return count;
    }
    public static void main(String[] args) {
        System.out.println(findNumberOfLIS(new int[]{1,3,5,4,7})); // 2
    }
}

Line Notes

static int maxLen = 0, count = 0;Global variables to track max length and count

if (index == nums.length)Base case: end of array reached

dfs(nums, index + 1, prevIndex, length);Skip current element

if (prevIndex == -1 || nums[index] > nums[prevIndex])Include current if increasing

count++Increment count when a max length subsequence found

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

int maxLen = 0, countLIS = 0;

void dfs(const vector<int>& nums, int index, int prevIndex, int length) {
    if (index == nums.size()) {
        if (length > maxLen) {
            maxLen = length;
            countLIS = 1;
        } else if (length == maxLen) {
            countLIS++;
        }
        return;
    }
    // Skip current
    dfs(nums, index + 1, prevIndex, length);
    // Take current if increasing
    if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
        dfs(nums, index + 1, index, length + 1);
    }
}

int findNumberOfLIS(vector<int>& nums) {
    maxLen = 0; countLIS = 0;
    dfs(nums, 0, -1, 0);
    return countLIS;
}

int main() {
    vector<int> nums = {1,3,5,4,7};
    cout << findNumberOfLIS(nums) << endl; // 2
    return 0;
}

Line Notes

int maxLen = 0, countLIS = 0;Global variables for max length and count

if (index == nums.size())Base case: end of recursion

dfs(nums, index + 1, prevIndex, length);Skip current element

if (prevIndex == -1 || nums[index] > nums[prevIndex])Include current element if valid

countLIS++Count subsequences matching max length

function findNumberOfLIS(nums) {
    let maxLen = 0, count = 0;
    function dfs(index, prevIndex, length) {
        if (index === nums.length) {
            if (length > maxLen) {
                maxLen = length;
                count = 1;
            } else if (length === maxLen) {
                count++;
            }
            return;
        }
        // Skip current
        dfs(index + 1, prevIndex, length);
        // Take current if increasing
        if (prevIndex === -1 || nums[index] > nums[prevIndex]) {
            dfs(index + 1, index, length + 1);
        }
    }
    dfs(0, -1, 0);
    return count;
}

// Example usage
console.log(findNumberOfLIS([1,3,5,4,7])); // 2

Line Notes

let maxLen = 0, count = 0;Track max LIS length and count globally

if (index === nums.length)Base case: processed all elements

dfs(index + 1, prevIndex, length);Skip current element

if (prevIndex === -1 || nums[index] > nums[prevIndex])Include current element if increasing

count++Increment count for max length subsequence

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each element can be included or excluded, leading to 2^n subsequences; recursion stack depth is O(n).

💡 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 useful to understand the problem structure.

🧠

DP with O(n^2) Time and Counting

💡 This approach uses dynamic programming to efficiently compute LIS length and count by building solutions from smaller subproblems.

Intuition

For each element, look back at all previous smaller elements to find the longest subsequence it can extend, and sum counts accordingly.

Algorithm

1. Initialize dp and count arrays with 1s (each element alone forms LIS length 1).
2. For each element i, check all j < i where nums[j] < nums[i].
3. Update dp[i] to max(dp[i], dp[j] + 1) and update count[i] accordingly.
4. Find the maximum length in dp and sum counts of all indices with that length.

💡 This approach explicitly tracks both length and count, which is key to solving the problem.

Recurrence:dp[i] = max(dp[j]) + 1 for all j < i with nums[j] < nums[i]; count[i] = sum of count[j] for all such j where dp[j] is max

</>

Code

def findNumberOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    count = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    count[i] = count[j]
                elif dp[j] + 1 == dp[i]:
                    count[i] += count[j]
    max_len = max(dp)
    return sum(c for i, c in enumerate(count) if dp[i] == max_len)

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

Line Notes

dp = [1] * nInitialize LIS length for each element as 1

count = [1] * nInitialize count of LIS ending at each element as 1

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

if nums[j] < nums[i]:Only consider increasing subsequences

if dp[j] + 1 > dp[i]:Found longer LIS ending at i, update dp and count

public class NumberOfLIS {
    public static int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] count = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }
        int maxLen = 0, result = 0;
        for (int len : dp) maxLen = Math.max(maxLen, len);
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) result += count[i];
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println(findNumberOfLIS(new int[]{1,3,5,4,7})); // 2
    }
}

Line Notes

Arrays.fill(dp, 1);Initialize dp array with 1s for LIS length

Arrays.fill(count, 1);Initialize count array with 1s

for (int i = 0; i < n; i++)Outer loop over elements

if (nums[j] < nums[i])Check increasing condition

count[i] += count[j];Add counts when LIS length ties

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

int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1), count(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    count[i] = count[j];
                } else if (dp[j] + 1 == dp[i]) {
                    count[i] += count[j];
                }
            }
        }
    }
    int maxLen = *max_element(dp.begin(), dp.end());
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] == maxLen) result += count[i];
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,5,4,7};
    cout << findNumberOfLIS(nums) << endl; // 2
    return 0;
}

Line Notes

vector<int> dp(n, 1), count(n, 1);Initialize dp and count arrays

for (int i = 0; i < n; i++)Outer loop for LIS end index

if (nums[j] < nums[i])Check if nums[i] can extend subsequence

dp[i] = dp[j] + 1;Update LIS length

count[i] += count[j];Accumulate counts for LIS

function findNumberOfLIS(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    const count = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    count[i] = count[j];
                } else if (dp[j] + 1 === dp[i]) {
                    count[i] += count[j];
                }
            }
        }
    }
    const maxLen = Math.max(...dp);
    let result = 0;
    for (let i = 0; i < n; i++) {
        if (dp[i] === maxLen) result += count[i];
    }
    return result;
}

// Example usage
console.log(findNumberOfLIS([1,3,5,4,7])); // 2

Line Notes

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

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

for (let i = 0; i < n; i++)Outer loop over array elements

if (nums[j] < nums[i])Check increasing condition

count[i] += count[j];Add counts for equal length LIS

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Nested loops over n elements lead to O(n^2) time; dp and count arrays use O(n) space.

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

Interview Verdict: Accepted

This is the standard solution for this problem and is efficient enough for typical constraints.

🧠

Optimized DP with Binary Indexed Tree / Segment Tree (O(n log n))

💡 This approach uses advanced data structures to optimize the DP solution to O(n log n), suitable for large inputs.

Intuition

Use coordinate compression and a Fenwick tree to quickly query and update LIS length and counts for all smaller elements.

Algorithm

1. Coordinate compress nums to reduce range.
2. Initialize Fenwick tree to store pairs of (length, count).
3. For each number in nums, query Fenwick tree for max length and count of smaller numbers.
4. Update Fenwick tree with new length and count for current number.
5. At the end, find max length and sum counts from Fenwick tree.

💡 This approach combines DP with efficient queries and updates using Fenwick tree, a key advanced technique.

Recurrence:dp[i] = max query Fenwick tree for nums[j] < nums[i] + 1; count[i] = sum counts for max length

</>

Code

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [(0, 0) for _ in range(size + 1)]

    def update(self, i, length, count):
        while i <= self.size:
            cur_len, cur_count = self.tree[i]
            if length > cur_len:
                self.tree[i] = (length, count)
            elif length == cur_len:
                self.tree[i] = (cur_len, cur_count + count)
            i += i & (-i)

    def query(self, i):
        max_len, total_count = 0, 0
        while i > 0:
            cur_len, cur_count = self.tree[i]
            if cur_len > max_len:
                max_len, total_count = cur_len, cur_count
            elif cur_len == max_len:
                total_count += cur_count
            i -= i & (-i)
        return max_len, total_count

def findNumberOfLIS(nums):
    sorted_unique = sorted(set(nums))
    def get_index(x):
        # 1-based index for Fenwick tree
        import bisect
        return bisect.bisect_left(sorted_unique, x) + 1

    fenw = FenwickTree(len(sorted_unique))
    for num in nums:
        idx = get_index(num) - 1
        length, count = fenw.query(idx)
        fenw.update(get_index(num), length + 1, max(count,1))
    max_len, total_count = fenw.query(len(sorted_unique))
    return total_count

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

Line Notes

class FenwickTree:Defines Fenwick tree data structure for efficient queries

def update(self, i, length, count):Updates Fenwick tree with new LIS length and count

def query(self, i):Queries Fenwick tree for max LIS length and count up to index i

for num in nums:Process each number in input array

fenw.update(get_index(num), length + 1, max(count,1))Update Fenwick tree with LIS info for current number

import java.util.*;
public class NumberOfLIS {
    static class FenwickTree {
        int size;
        int[] length;
        int[] count;
        FenwickTree(int n) {
            size = n;
            length = new int[n + 1];
            count = new int[n + 1];
        }
        void update(int i, int len, int cnt) {
            while (i <= size) {
                if (len > length[i]) {
                    length[i] = len;
                    count[i] = cnt;
                } else if (len == length[i]) {
                    count[i] += cnt;
                }
                i += i & (-i);
            }
        }
        int[] query(int i) {
            int maxLen = 0, totalCount = 0;
            while (i > 0) {
                if (length[i] > maxLen) {
                    maxLen = length[i];
                    totalCount = count[i];
                } else if (length[i] == maxLen) {
                    totalCount += count[i];
                }
                i -= i & (-i);
            }
            return new int[]{maxLen, totalCount};
        }
    }
    public static int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) set.add(num);
        List<Integer> sorted = new ArrayList<>(set);
        FenwickTree fenw = new FenwickTree(sorted.size());
        for (int num : nums) {
            int idx = Collections.binarySearch(sorted, num);
            int[] res = fenw.query(idx); // idx is 0-based, query expects 1-based, so query(idx) is off by one
            int length = res[0], count = res[1];
            if (count == 0) count = 1;
            fenw.update(idx + 1, length + 1, count);
        }
        int[] ans = fenw.query(sorted.size());
        return ans[1];
    }
    public static void main(String[] args) {
        System.out.println(findNumberOfLIS(new int[]{1,3,5,4,7})); // 2
    }
}

Line Notes

class FenwickTree {Fenwick tree class to store LIS length and count

void update(int i, int len, int cnt)Update Fenwick tree nodes with LIS info

int[] query(int i)Query Fenwick tree for max LIS length and count

for (int num : nums)Iterate over input array

fenw.update(idx + 1, length + 1, count);Update Fenwick tree with current LIS data

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

struct FenwickTree {
    int n;
    vector<int> length, count;
    FenwickTree(int size) : n(size), length(size + 1, 0), count(size + 1, 0) {}
    void update(int i, int len, int cnt) {
        while (i <= n) {
            if (len > length[i]) {
                length[i] = len;
                count[i] = cnt;
            } else if (len == length[i]) {
                count[i] += cnt;
            }
            i += i & (-i);
        }
    }
    pair<int,int> query(int i) {
        int maxLen = 0, totalCount = 0;
        while (i > 0) {
            if (length[i] > maxLen) {
                maxLen = length[i];
                totalCount = count[i];
            } else if (length[i] == maxLen) {
                totalCount += count[i];
            }
            i -= i & (-i);
        }
        return {maxLen, totalCount};
    }
};

int findNumberOfLIS(vector<int>& nums) {
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    FenwickTree fenw(sorted.size());
    for (int num : nums) {
        int idx = (int)(lower_bound(sorted.begin(), sorted.end(), num) - sorted.begin());
        auto [length, count] = fenw.query(idx);
        if (count == 0) count = 1;
        fenw.update(idx + 1, length + 1, count);
    }
    auto [maxLen, totalCount] = fenw.query((int)sorted.size());
    return totalCount;
}

int main() {
    vector<int> nums = {1,3,5,4,7};
    cout << findNumberOfLIS(nums) << endl; // 2
    return 0;
}

Line Notes

struct FenwickTree {Fenwick tree structure for efficient DP queries

void update(int i, int len, int cnt)Update Fenwick tree nodes

pair<int,int> query(int i)Query Fenwick tree for max LIS length and count

for (int num : nums)Process each element in nums

fenw.update(idx + 1, length + 1, count);Update Fenwick tree with LIS info

class FenwickTree {
    constructor(size) {
        this.size = size;
        this.length = new Array(size + 1).fill(0);
        this.count = new Array(size + 1).fill(0);
    }
    update(i, len, cnt) {
        while (i <= this.size) {
            if (len > this.length[i]) {
                this.length[i] = len;
                this.count[i] = cnt;
            } else if (len === this.length[i]) {
                this.count[i] += cnt;
            }
            i += i & (-i);
        }
    }
    query(i) {
        let maxLen = 0, totalCount = 0;
        while (i > 0) {
            if (this.length[i] > maxLen) {
                maxLen = this.length[i];
                totalCount = this.count[i];
            } else if (this.length[i] === maxLen) {
                totalCount += this.count[i];
            }
            i -= i & (-i);
        }
        return [maxLen, totalCount];
    }
}

function findNumberOfLIS(nums) {
    const sortedUnique = Array.from(new Set(nums)).sort((a,b) => a-b);
    function getIndex(x) {
        let left = 0, right = sortedUnique.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (sortedUnique[mid] === x) return mid + 1;
            else if (sortedUnique[mid] < x) left = mid + 1;
            else right = mid - 1;
        }
        return left + 1;
    }
    const fenw = new FenwickTree(sortedUnique.length);
    for (const num of nums) {
        const idx = getIndex(num) - 1;
        const [length, count] = fenw.query(idx);
        fenw.update(getIndex(num), length + 1, Math.max(count, 1));
    }
    const [maxLen, totalCount] = fenw.query(sortedUnique.length);
    return totalCount;
}

// Example usage
console.log(findNumberOfLIS([1,3,5,4,7])); // 2

Line Notes

class FenwickTree {Fenwick tree class for LIS length and count

update(i, len, cnt) {Update Fenwick tree nodes with LIS info

query(i) {Query Fenwick tree for max LIS length and count

for (const num of nums) {Iterate over input array

fenw.update(getIndex(num), length + 1, Math.max(count, 1));Update Fenwick tree with LIS data

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Coordinate compression and Fenwick tree queries/updates take O(log n) per element, total O(n log n).

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

Interview Verdict: Accepted

This is the optimal solution for large inputs and demonstrates mastery of advanced DP optimization.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the O(n^2) DP approach in most interviews unless input size demands optimization.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. DP O(n^2)	O(n^2)	O(n)	No	Yes	Code this in most interviews
3. Optimized O(n log n)	O(n log n)	O(n)	No	Yes, with extra bookkeeping	Mention or code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then move to DP and optimizations.

How to Present

Clarify problem constraints and ask about input size.Explain brute force approach and why it's inefficient.Describe DP approach with length and count arrays.Discuss possible optimizations if input size is large.Write clean code and test with edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer tests understanding of LIS, ability to track counts, and optimization skills.

Common Follow-ups

• How to optimize from O(n^2) to O(n log n)? → Use Fenwick tree or segment tree with coordinate compression.
• How to reconstruct one LIS? → Track predecessors during DP and backtrack.

💡 These follow-ups test deeper understanding of DP optimization and solution reconstruction.

🔍

Pattern Recognition

When to Use

1) Asked for LIS or variants; 2) Need to count number of LIS; 3) Input size large; 4) Requires DP with counting.

Signature Phrases

'longest strictly increasing subsequence''number of such subsequences'

NOT This Pattern When

Problems asking for longest common subsequence or maximum sum increasing subsequence are related but different.

Similar Problems

Longest Increasing Subsequence - find length onlyNumber of Increasing Subsequences - count all increasing subsequencesLongest Bitonic Subsequence - combines LIS and LDS

Practice

1. You are given a binary tree where each node contains a non-negative integer value representing money. You want to maximize the amount of money you can rob without robbing two directly connected nodes (parent and child). Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming on trees using post-order traversal to consider robbing or skipping each node

B. Greedy algorithm that always robs the node with the highest value first

C. Simple recursion without memoization that tries all combinations

D. Breadth-first search to select nodes level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing sum of node values without robbing adjacent nodes, which is a classic tree DP problem.

2. Step 2: Identify suitable algorithm

   Greedy and BFS fail because they don't consider subtree dependencies; simple recursion is exponential. DP on trees with post-order traversal correctly aggregates rob/not_rob states bottom-up.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP on trees handles adjacency constraints optimally [OK]

Hint: Tree DP with post-order traversal handles adjacency constraints [OK]

Common Mistakes:

• Thinking greedy or BFS can solve adjacency constraints optimally

2. Consider the following Python code implementing the optimized LIS algorithm. What is the value of the variable tails after processing the input [3, 1, 2]?

easy

A. [1, 2, 3]

B. [1, 2]

C. [1, 3]

D. [3, 1, 2]

Solution

1. Step 1: Process num=3

   tails is empty, bisect_left returns 0, append 3 -> tails = [3]

2. Step 2: Process num=1

   bisect_left(tails,1) returns 0, replace tails[0] with 1 -> tails = [1]

3. Step 3: Process num=2

   bisect_left(tails,2) returns 1 (end of tails), append 2 -> tails = [1, 2]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   tails always sorted and minimal last elements [OK]

Hint: tails stores smallest possible ends of subsequences [OK]

Common Mistakes:

• Appending instead of replacing in tails
• Misunderstanding bisect_left index
• Confusing tails with actual subsequence

3. What is the time complexity of the bottom-up bitmask DP solution for the shortest path visiting all nodes problem on a graph with n nodes?

medium

A. O(n * 2^n)

B. O(n^2 * 2^n)

C. O(n! * n)

D. O(2^n * E) where E is the number of edges

Solution

1. Step 1: Identify loops in the bottom-up DP

   The outer loop iterates over all masks (2^n), the inner loop over nodes (n), and for each node, we iterate over its neighbors (E edges total). Thus, the complexity depends on the number of edges.

2. Step 2: Confirm complexity formula

   Since each state dp[u][mask] is updated by checking neighbors, total complexity is O(2^n * E), where E is the number of edges.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches known complexity for bitmask DP on graphs [OK]

Hint: Complexity depends on subsets and edges, not just nodes squared [OK]

Common Mistakes:

• Confusing with O(n^2 * 2^n)
• Ignoring neighbor iteration
• Assuming factorial complexity

4. What is the time complexity of the bottom-up bitmask DP solution for the Travelling Salesman Problem with n cities, and why? Options:

medium

A. O(n * 2^n) because we process each subset and city once

B. O(2^n) because subsets dominate the complexity

C. O(n^2 * 2^n) because for each subset and city, we check all possible previous cities

D. O(n! ) because we consider all permutations of cities

Solution

1. Step 1: Identify loops in the code

   There are three nested loops: over all subsets (2^n), over all cities (n), and over all possible previous cities (n).

2. Step 2: Multiply loop complexities

   Total complexity is O(2^n * n * n) = O(n^2 * 2^n). O(n * 2^n) because we process each subset and city once misses the inner loop over previous cities, underestimating complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask DP complexity is well-known as O(n^2 * 2^n) [OK]

Hint: Remember triple nested loops: subsets, current city, previous city [OK]

Common Mistakes:

• Ignoring inner loop over previous cities leads to underestimation

5. The following code attempts to solve the Travelling Salesman Problem using bottom-up bitmask DP. Identify the bug that causes incorrect results on some inputs.

def tsp_bottom_up_buggy(dist):
    n = len(dist)
    ALL_VISITED = (1 << n) - 1
    dp = [[float('inf')] * n for _ in range(1 << n)]
    # BUG: dp[1][0] not initialized

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                for j in range(n):
                    if mask & (1 << j) and i != j:
                        prev_mask = mask ^ (1 << i)
                        dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])

    ans = float('inf')
    for i in range(1, n):
        ans = min(ans, dp[ALL_VISITED][i] + dist[i][0])
    return ans

medium

A. Missing base case initialization dp[1][0] = 0

B. Incorrect calculation of prev_mask = mask ^ (1 << i)

C. Line initializing dp array with float('inf')

D. Final loop over i in range(1, n) missing city 0

Solution

1. Step 1: Check base case initialization

   The DP table must have dp[1][0] = 0 to represent starting at city 0 with only city 0 visited.

2. Step 2: Consequence of missing base case

   Without this, all dp states remain infinite, so no valid path cost is computed, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Base case initialization is essential for DP correctness [OK]

Hint: Always initialize base case dp for starting city [OK]

Common Mistakes:

• Forgetting dp[1][0] initialization leads to infinite costs