Longest Increasing Subsequence

Find the length of the longest increasing subsequence.

Pattern

LIS DP / Binary Search

This problem follows the LIS DP / Binary Search pattern, commonly found in the 1-D Dynamic Programming category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

dp[i] = longest subsequence ending at i. Or use patience sorting with binary search for O(n log n).

Key Insight

The tails array isn't the actual LIS — it tracks the smallest possible tail for each length. Binary search on this array gives O(n log n).

Step-by-step

1Create dp array where dp[i] = length of LIS ending at index i
2For each element, check all previous elements
3If nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1)
4Or use patience sorting: maintain a list of smallest tail values

Pseudocode

# O(n log n) approach
tails = []
for num in nums:
    pos = bisect_left(tails, num)
    if pos == len(tails):
        tails.append(num)
    else:
        tails[pos] = num
return len(tails)

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

Master this pattern with YeetCode

Practice Longest Increasing Subsequence and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.

Practice this problem

Previous← Word Break