Practice Longest Increasing Subsequence
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Given an integer array nums, return the length of the longest strictly increasing subsequence. Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Source: Longest Increasing Subsequence on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
nums = [10,9,2,5,3,7,101,18]
4
# Example 2
nums = [0,1,0,3,2,3]
4
# Example 3
nums = [7,7,7,7,7,7,7]
1
Constraints
How to solve Longest Increasing Subsequence
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
For each possible length, track the smallest value that can end an increasing subsequence of that length; this list stays sorted, so each new element either extends it or replaces the first entry that is at least as large, located by binary search.
Why brute force is not enough
Enumerating 2^n subsequences is impossible for n up to 2500. The quadratic dynamic program, where each position looks back at every earlier smaller element, is O(n^2), about 6 * 10^6 steps, which passes but does not meet the O(n log n) follow-up an interviewer will push toward.
Approach
- Keep a list called tails where entry i is the smallest possible last value of a strictly increasing subsequence of length i + 1; because a shorter subsequence can always end no higher than a longer one, the list is strictly increasing.
- For each element in order, binary search for the leftmost tails entry that is greater than or equal to it.
- If none exists, the element extends the longest subsequence so far, so append it.
- Otherwise overwrite that entry; the length it represents is unchanged but now ends on a smaller value, which only helps later extensions.
- The final length of tails is the answer. The list itself is generally not a valid subsequence, so reconstructing one needs a separate predecessor record.
Walkthrough of Example 1
nums = [10,9,2,5,3,7,101,18] → 4
- 10 starts tails as [10]; 9 replaces it giving [9]; 2 replaces it giving [2].
- 5 exceeds everything, so append: [2,5]. 3 replaces 5, the first entry at least 3: [2,3].
- 7 is appended: [2,3,7]. 101 is appended: [2,3,7,101].
- 18 replaces 101: [2,3,7,18]. The length 4 is the answer, matching subsequences such as 2, 3, 7, 101.
Time and space
Time O(n log n) · Space O(n). n is nums.length; each element does one binary search over a list of at most n entries, and tails is the only extra storage.
Interview pitfalls
- Using the wrong binary search bound: strictly increasing requires replacing the first entry greater than or equal to the element; searching for strictly greater instead permits equal values and returns 7 rather than 1 for example 3.
- Reporting tails as the subsequence; after example 1 it reads [2,3,7,18], a valid subsequence here only by coincidence.
- Off-by-one when the element exceeds the last entry, which must append rather than overwrite an out-of-range index.
- Not being able to explain how to upgrade the O(n^2) solution when asked.
Follow-up questions interviewers ask
- How would you reconstruct one actual longest increasing subsequence, not just its length?
- How does the method change for a longest non-decreasing subsequence?
- Can you count how many distinct longest increasing subsequences exist, and why does the tails trick no longer suffice?
Further reading on the technique: Longest increasing subsequence
Related LeetCode Problems
Practice more problems similar to Longest Increasing Subsequence.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.