Longest Increasing Subsequence

📋

Problem

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

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

Edge cases: Single element array → output is 1All elements equal → output is 1Strictly decreasing array → output is 1

</>

IDE

def lengthOfLIS(nums: list[int]) -> int:public int lengthOfLIS(int[] nums)int lengthOfLIS(vector<int>& nums)function lengthOfLIS(nums)

def lengthOfLIS(nums):
    # Write your solution here
    pass

class Solution {
    public int lengthOfLIS(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function lengthOfLIS(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for non-empty input due to missing base case or incorrect initialization.✅ Add base case: if not nums: return 0 and initialize dp array with 1s.

Wrong: 5Counting non-strictly increasing subsequence by allowing nums[j] <= nums[i].✅ Change condition to strict inequality: nums[j] < nums[i] before updating dp[i].

Wrong: 3Greedy approach picking local max instead of global LIS.✅ Use DP or patience sorting with binary search instead of greedy selection.

Wrong: 2Off-by-one error in dp indexing or updating dp[i] incorrectly.✅ Ensure dp[i] updates consider all j < i and correct indexing.

Wrong: TLEUsing brute force or O(n^2) DP on large input.✅ Implement O(n log n) patience sorting with binary search optimization.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Watch out for common pitfalls like greedy mistakes and equality handling.

Optimize your solution to handle large inputs efficiently.

t1_01basic

Input{"nums":[10,9,2,5,3,7,101,18]}

Expected4

⏱ Performance - must finish in 2000ms

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

💡 Think about how to build the LIS ending at each index.

💡 Use dynamic programming to store the length of LIS up to each element.

💡 dp[i] = max(dp[j]) + 1 for all j < i where nums[j] < nums[i].

Why it failed: Incorrect output means DP recurrence is wrong or comparison condition is incorrect. Fix by ensuring dp[i] updates only when nums[j] < nums[i].

✓ Correctly computed LIS length using DP.

t1_02basic

Input{"nums":[0,1,0,3,2,3]}

Expected4

⏱ Performance - must finish in 2000ms

The LIS is [0,1,2,3], length 4.

💡 Check subsequences that skip some elements to get longer LIS.

💡 Remember LIS is strictly increasing, so equal elements don't extend the sequence.

💡 Update dp[i] only if nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1).

Why it failed: Failing this test usually means not enforcing strict increasing condition or incorrect dp updates. Fix by checking nums[j] < nums[i] before updating dp[i].

✓ DP correctly handles non-monotonic sequences.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has LIS length 0.

💡 Consider what LIS means when no elements exist.

💡 Base case: empty input should return 0 immediately.

💡 Add a check for empty input and return 0 before DP.

Why it failed: Returning non-zero means no base case for empty input. Fix by adding if not nums: return 0.

✓ Correctly handles empty input.

t2_02edge

Input{"nums":[42]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array has LIS length 1.

💡 With one element, LIS is always length 1.

💡 DP initialization should set dp[0] = 1.

💡 Ensure code handles single-element arrays without errors.

Why it failed: Failing means dp initialization or base case is missing. Fix by initializing dp array with 1s.

✓ Correctly handles single element input.

t2_03edge

Input{"nums":[5,4,3,2,1]}

Expected1

⏱ Performance - must finish in 2000ms

Strictly decreasing array has LIS length 1 (any single element).

💡 No increasing pairs exist, so LIS length is 1.

💡 DP should never increase beyond 1 for decreasing sequences.

💡 Check that dp[i] does not update when nums[j] >= nums[i].

Why it failed: Failing means code allows non-increasing sequences to increase dp. Fix by enforcing strict inequality nums[j] < nums[i].

✓ Correctly handles strictly decreasing sequences.

t3_01corner

Input{"nums":[1,3,2,4,3,5]}

Expected4

⏱ Performance - must finish in 2000ms

LIS is [1,2,3,5] or [1,3,4,5], length 4.

💡 Greedy approach picking local max may fail here.

💡 DP or patience sorting ensures global optimal LIS, not just local.

💡 Use binary search or DP to find correct LIS length, not greedy picks.

Why it failed: Greedy approach fails by choosing local max incorrectly. Fix by implementing DP or patience sorting with binary search.

✓ Correctly handles sequences where greedy fails.

t3_02corner

Input{"nums":[2,2,2,2,2]}

Expected1

⏱ Performance - must finish in 2000ms

All elements equal, LIS length is 1.

💡 Check strict increasing condition carefully.

💡 Equal elements do not extend LIS.

💡 Ensure dp updates only when nums[j] < nums[i], not <=.

Why it failed: Failing means code treats equal elements as increasing. Fix by changing condition to strict inequality nums[j] < nums[i].

✓ Correctly handles all equal elements.

t3_03corner

Input{"nums":[1,2,2,3]}

Expected3

⏱ Performance - must finish in 2000ms

LIS is [1,2,3], length 3 (strictly increasing).

💡 Watch out for off-by-one errors in indices.

💡 Ensure dp updates consider only strictly increasing elements.

💡 Check that duplicates do not increase LIS length incorrectly.

Why it failed: Failing means off-by-one or equality allowed in LIS. Fix by enforcing strict inequality and correct indexing in dp updates.

✓ Correctly handles duplicates with strict increasing condition.

t4_01performance

Input{"nums":[1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,999999990,999999989,999999988,999999987,999999986,999999985,999999984,999999983,999999982,999999981,999999980,999999979,999999978,999999977,999999976,999999975,999999974,999999973,999999972,999999971,999999970,999999969,999999968,999999967,999999966,999999965,999999964,999999963,999999962,999999961,999999960,999999959,999999958,999999957,999999956,999999955,999999954,999999953,999999952,999999951,999999950,999999949,999999948,999999947,999999946,999999945,999999944,999999943,999999942,999999941,999999940,999999939,999999938,999999937,999999936,999999935,999999934,999999933,999999932,999999931,999999930,999999929,999999928,999999927,999999926,999999925,999999924,999999923,999999922,999999921,999999920,999999919,999999918,999999917,999999916,999999915,999999914,999999913,999999912,999999911,999999910,999999909,999999908,999999907,999999906,999999905,999999904,999999903,999999902,999999901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100, strictly decreasing sequence, O(n^2) brute force will time out, optimized O(n log n) needed.

💡 Brute force O(2^n) or O(n^2) DP will time out for n=100.

💡 Use patience sorting or binary search optimization for O(n log n).

💡 Implement binary search to maintain tails array for LIS length.

Why it failed: TLE indicates brute force or O(n^2) DP used. Fix by implementing O(n log n) patience sorting with binary search.

✓ Efficient O(n log n) solution confirmed.

Practice

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

2. The following code attempts to solve the Russian Doll Envelopes problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes by width ascending and height ascending

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing element in lis at found index

Solution

1. Step 1: Examine sorting order

   Sorting by width ascending and height ascending causes envelopes with same width but increasing height to be counted incorrectly in LIS.

2. Step 2: Understand LIS requirement

   Heights must be sorted descending for equal widths to avoid counting invalid envelopes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order bug leads to wrong LIS and incorrect nesting count [OK]

Hint: Sort height descending for equal widths to avoid LIS errors [OK]

Common Mistakes:

• Sorting both dimensions ascending instead of height descending
• Misusing bisect functions
• Incorrectly extracting heights

3. Suppose the problem is modified so that elements can be reused multiple times in subsequences (i.e., subsequences are multisets, not strictly increasing indices). Which change to the DP approach correctly counts all arithmetic subsequences under this new constraint?

hard

A. Keep the same DP but allow j to be equal to i to reuse elements

B. Use a DP that counts subsequences by difference without restricting j < i, allowing repeated indices

C. Modify DP to consider all pairs (i, j) with i ≤ j and update counts accordingly

D. Switch to a combinatorial formula since DP no longer applies

Solution

1. Step 1: Understand reuse means indices can repeat or be equal

   Original DP requires j < i to ensure strictly increasing indices; reuse breaks this.

2. Step 2: Modify DP loops to allow i ≤ j and update counts accordingly

   Allowing i ≤ j and updating dp[i][diff] with dp[j][diff] + 1 counts subsequences with repeated elements correctly.

3. Step 3: Reject naive reuse of original DP or combinatorial formulas

   Original DP with j < i fails; combinatorial formulas are not straightforward here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Allowing i ≤ j and updating counts handles reuse correctly [OK]

Hint: Reuse requires relaxing j < i to i ≤ j in DP loops [OK]

Common Mistakes:

• Trying to reuse original DP without index relaxation
• Assuming combinatorial formula suffices
• Allowing j = i without updating counts properly

4. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and the tree is now a general graph with possible cycles. Which of the following approaches correctly adapts the maximum path sum solution to handle this variant?

hard

A. Use the same DP on tree approach with memoization, ignoring cycles since the graph is connected

B. Convert the graph to a tree by removing edges to break cycles, then apply the original DP on tree solution

C. Perform a DFS with cycle detection and use dynamic programming with visited states to avoid infinite loops, tracking maximum sums on simple paths

D. Use a greedy approach to select the highest value nodes repeatedly until no improvement

Solution

1. Step 1: Understand the impact of cycles

   Allowing node reuse and cycles means paths can be infinite unless cycles are detected and handled.

2. Step 2: Identify correct approach

   DFS with cycle detection and DP with visited states prevents infinite loops and correctly computes max sums on simple paths in graphs.

3. Step 3: Why other options fail

   Original DP assumes tree structure; greedy ignores path connectivity; converting graph to tree loses valid paths.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Cycle-aware DFS with DP is necessary for graphs with cycles [OK]

Hint: Cycle detection plus DP needed for graphs with cycles [OK]

Common Mistakes:

• Ignoring cycles causes infinite loops
• Greedy fails on path connectivity
• Tree DP invalid on graphs

5. Suppose pairs can be reused multiple times in the chain (i.e., you can select the same pair multiple times if it fits). Which modification to the algorithm correctly finds the longest chain length under this new constraint?

hard

A. Use the same greedy approach sorting by end time, but allow pairs with start >= current_end

B. Use a bottom-up DP without sorting, checking all pairs for chain extension

C. Sort pairs by start time and greedily select pairs with earliest start repeatedly

D. Use dynamic programming with memoization to explore all sequences allowing reuse

Solution

1. Step 1: Understand reuse breaks greedy assumptions

   Greedy relies on no reuse; allowing reuse requires exploring multiple sequences.

2. Step 2: Use DP with memoization

   DP can handle repeated pairs by caching results for each state, ensuring correctness.

3. Step 3: Reject naive greedy and unsorted DP

   Greedy fails with reuse; unsorted DP is inefficient and incorrect without sorting.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Memoized DP handles reuse correctly [OK]

Hint: Reuse breaks greedy; DP needed [OK]

Common Mistakes:

• Trying to fix greedy by relaxing conditions
• Ignoring sorting or memoization in DP
• Assuming bottom-up DP without sorting suffices