Longest Increasing Subsequence
Asked at Atlassian
Problem
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order. The O(n log n) solution uses patience sorting with binary search.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
DP approach: dp[i] = length of LIS ending at index i. For each i, check all j < i. If nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1). Time: O(n²). Good but not optimal.
Binary search optimization: maintain a tails array where tails[k] = smallest possible tail of all increasing subsequences of length k+1. This array is always sorted, so binary search works.
For each number in nums: if it's larger than all elements in tails, append it (extends the longest subsequence). Otherwise, use binary search to find the first element >= num in tails and replace it. This keeps tails minimal for future extensions.
Why replacing works: replacing a larger tail with a smaller one doesn't change the length of any existing subsequence, but it gives future numbers a better chance of extending. tails is NOT the actual LIS, just a tool to track length.
Visual walkthrough: nums = [10, 9, 2, 5, 3, 7, 101, 18].
- 10: tails = [10]
- 9: replace 10. tails = [9]
- 2: replace 9. tails = [2]
- 5: append. tails = [2, 5]
- 3: replace 5. tails = [2, 3]
- 7: append. tails = [2, 3, 7]
- 101: append. tails = [2, 3, 7, 101]
- 18: replace 101. tails = [2, 3, 7, 18]
Length of tails = 4. LIS: [2, 3, 7, 101] or [2, 3, 7, 18].
Time: O(n log n) (n iterations, each with O(log n) binary search). Space: O(n) for the tails array.
Optimal Approach
Binary search with tails array:
- Initialize
tailsas empty. - For each num in nums:
a. Iftailsis empty or num > last element oftails, append num.
b. Otherwise, use binary search to find the first element intails>= num, and replace it with num. - Return length of
tails.
Binary search: use left = 0, right = len(tails) - 1. While left <= right, compute mid. If tails[mid] >= num, go left. Else go right. Replace at left.
Walkthrough: nums = [0, 8, 4, 12, 2].
- 0: tails = [0]
- 8: append. tails = [0, 8]
- 4: replace 8. tails = [0, 4]
- 12: append. tails = [0, 4, 12]
- 2: replace 4. tails = [0, 2, 12]
Length = 3. LIS: [0, 4, 12] or [0, 2, 12].
Time: O(n log n). Space: O(n).
What Trips People Up in Real Interviews
Confusing subsequence with subarray. A subsequence does NOT need to be contiguous. [2, 3, 7, 101] is a valid subsequence of [10, 9, 2, 5, 3, 7, 101, 18] even though the indices aren't consecutive.
Thinking tails stores the actual LIS. It doesn't. tails stores the minimum possible tail for each length. The actual LIS can be reconstructed by tracking predecessors, but the problem only asks for length.
Using binary search incorrectly. You need bisect_left (find first >= num), not bisect_right (find first > num). Using bisect_right fails on duplicate values and doesn't maintain the strictly increasing property.
Forgetting that tails is sorted. If you don't maintain the sorted invariant, binary search won't work. Appending when num > all tails and replacing otherwise maintains sorted order.
Trying to return tails as the answer. The length of tails is the answer, not tails itself. For example, tails = [2, 3, 7, 18] but the actual LIS is [2, 3, 7, 101].
Solution Code
import bisect
def lengthOfLIS(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)Frequently Asked Questions
What is the Longest Increasing Subsequence problem?
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order. The `O(n log n)` solution uses patience sorting with binary search.
How do you solve Longest Increasing Subsequence?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Increasing Subsequence?
Longest Increasing Subsequence is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Longest Increasing Subsequence?
- Confusing subsequence with subarray. A subsequence does NOT need to be contiguous. [2, 3, 7, 101] is a valid subsequence of [10, 9, 2, 5, 3, 7, 101, 18] even though the indices aren't consecutive.
- Thinking `tails` stores the actual LIS. It doesn't. `tails` stores the minimum possible tail for each length. The actual LIS can be reconstructed by tracking predecessors, but the problem only asks for length.
- Using binary search incorrectly. You need `bisect_left` (find first >= num), not `bisect_right` (find first > num). Using `bisect_right` fails on duplicate values and doesn't maintain the strictly increasing property.
- Forgetting that `tails` is sorted. If you don't maintain the sorted invariant, binary search won't work. Appending when num > all tails and replacing otherwise maintains sorted order.
- Trying to return `tails` as the answer. The length of `tails` is the answer, not `tails` itself. For example, `tails = [2, 3, 7, 18]` but the actual LIS is [2, 3, 7, 101].