How Do You Find the Longest Increasing Subsequence?
Learn the longest increasing subsequence problem, its O(n^2) DP and O(n log n) binary search solutions, for coding interviews.
Expected Interview Answer
The longest increasing subsequence (LIS) is the longest subsequence of an array in which elements strictly increase, solvable in O(n^2) with straightforward dynamic programming or in O(n log n) using a patience-sorting technique with binary search over tracked tails.
The O(n^2) approach defines dp[i] as the length of the longest increasing subsequence ending exactly at index i, computed by scanning all earlier indices j where nums[j] < nums[i] and taking dp[i] = max(dp[j]) + 1. The O(n log n) approach instead maintains an array of the smallest possible tail value for an increasing subsequence of each length; for every new number, binary search finds the first tail greater than or equal to it and replaces that tail, or appends if the number extends the longest subsequence so far. The length of that tails array at the end is the LIS length, though the array itself is not necessarily a valid subsequence. This tails-array trick is the same idea behind patience sorting card games.
- O(n log n) solution scales to large inputs
- Reveals patience-sorting and binary search patterns
- Foundation for box-stacking and scheduling problems
- DP version is simple to reason about and extend
AI Mentor Explanation
A batsman's innings is tracked ball by ball, and analysts want the longest stretch of deliveries where his running strike rate strictly kept climbing. The simple approach checks, for every ball, every earlier ball with a lower rate and extends the best streak found there. A faster approach keeps a running list of the lowest strike-rate 'tail' seen for streaks of each length, replacing a tail whenever a new ball beats it, or extending the list when the ball tops everything so far. That growing tail list, found by binary search each time, converges to the length of the longest genuinely increasing streak without rechecking every prior ball.
Step-by-Step Explanation
Step 1
Define the O(n^2) DP state
dp[i] holds the LIS length ending exactly at index i, starting at 1 for every element.
Step 2
Scan earlier smaller elements
For each j < i with nums[j] < nums[i], set dp[i] = max(dp[i], dp[j] + 1).
Step 3
Optimize with a tails array
Maintain the smallest tail value for an increasing subsequence of each length; binary search to replace or extend it for each new number.
Step 4
Read the answer
dp[i^2] approach takes max(dp) over all i; the tails-array approach uses the final array length.
What Interviewer Expects
- Explain both the O(n^2) DP and O(n log n) patience-sorting approaches
- Correctly state that the tails array is not necessarily a valid subsequence
- Justify why binary search works because the tails array stays sorted
- Distinguish strictly increasing from non-decreasing variants
Common Mistakes
- Assuming the tails array in the O(n log n) method is itself the answer sequence
- Confusing LIS with the longest contiguous increasing run (a much easier sliding-window problem)
- Forgetting dp[i] must initialize to 1, not 0, since every element is a subsequence of length 1
- Using the wrong binary search variant (lower_bound vs upper_bound) for strict vs non-strict increases
Best Answer (HR Friendly)
“LIS finds the longest run of numbers that keep increasing, even if they're not next to each other in the array. The straightforward way compares every pair of numbers, but the clever trick keeps a running list of the smallest possible 'last number' for a streak of each length, using binary search to update it, which brings the whole thing down from quadratic to n log n time.”
Code Example
import bisect
def length_of_lis(nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
# O(n^2) reference version
def length_of_lis_dp(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Follow-up Questions
- How would you reconstruct the actual LIS, not just its length, in the O(n log n) version?
- How would you solve LIS in 2D, such as Russian doll envelopes?
- How does LIS relate to the patience sorting card game?
- How would you adapt the solution for a non-decreasing (not strictly increasing) subsequence?
MCQ Practice
1. What is the time complexity of the optimized LIS algorithm using a tails array and binary search?
Each of n elements does one binary search over the tails array, giving O(n log n) total.
2. In the O(n log n) LIS approach, what does the length of the tails array represent?
The tails array size equals the LIS length, though the array values themselves are not a valid subsequence.
3. In the O(n^2) DP formulation, what does dp[i] represent?
dp[i] is defined as the length of the longest increasing subsequence that ends exactly at index i.
Flash Cards
What is the O(n^2) recurrence for LIS? — dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i], starting dp[i] = 1.
What technique gives O(n log n) LIS? — Maintaining a tails array of smallest possible tail values per length, updated via binary search.
Is the tails array a valid subsequence? — No — only its length equals the LIS length, the values themselves are not an actual subsequence.
What game inspired the O(n log n) LIS technique? — Patience sorting (a card-sorting solitaire game).