300. Longest Increasing Subsequence
Model: qwen3.5:9b
Topics: Binary Search,Dynamic Programming
FAANG asked: 1
Acceptance rate: 44.5%
Problem Breakdown
We are given an integer array nums and need to find the length of its longest strictly increasing subsequence (LIS). A subsequence maintains relative order but does not require contiguous elements. “Strictly” means duplicates cannot be part of the same sequence (e.g., [2, 3] is valid; [2, 3, 3] is invalid for length calculation purposes if we treat it as strictly increasing).
Inputs: An integer array nums.
Outputs: A single integer representing the maximum length.
Constraints & Edge Cases:
- Array size up to 2500 (allows , but interviewers expect optimization).
- Values range from to (standard integers, no overflow issues in Python).
- Duplicates: Must be handled carefully;
[7, 7]yields length 1.
Intuition
First, I consider the brute-force approach: generate all possible subsequences and check which is longest increasing. This takes time due to exponential combinations—clearly infeasible for N=2500.
Next, Dynamic Programming (). Let dp[i] be the length of LIS ending at index i. To compute dp[i], we iterate through all previous indices j < i. If nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1). This works but is quadratic.
To improve this, I look for a greedy property: For any length , do we want the LIS ending at index to be as large or small? We actually care about keeping the ending value of an increasing subsequence of length as small as possible. Why? Because a smaller tail makes it easier for future elements to extend that sequence (since they just need to be larger than the tail).
This leads to maintaining an auxiliary array, tails, where tails[k] stores the smallest ending element of all increasing subsequences of length . Since we always want the smallest possible end value, this array remains sorted. This allows us to use binary search instead of linear scanning for updates.
Approach
We maintain a list called subsequence_ends. We iterate through each number in nums:
- If the current number is greater than all elements currently tracked (i.e., larger than the last element), it extends our longest subsequence found so far. We append it to
subsequence_ends. - Otherwise, we find the first element in
subsequence_endsthat is the current number and replace it with the current number. This “lowers” the tail for a specific length without changing the maximum length achieved yet.
This replacement logic ensures that if multiple subsequences of the same length exist, we keep track of the one ending with the smallest value (greedy optimization). Since subsequence_ends is always sorted in ascending order, finding this position takes using binary search (bisect_left).
Complexity Analysis
- Time: . We iterate through each of the elements once. For each element, we perform a binary search on
subsequence_ends, which has size at most , taking . Total: . - Space: to store the
subsequence_endsarray in the worst case (strictly increasing input).
Solution
import bisect
def lengthOfLIS(nums):
# 'tails' will store the smallest tail of all increasing subsequences
# of length i+1 at index i. It remains sorted, allowing binary search.
tails = []
for num in nums:
if not tails or num > tails[-1]:
# If current number is larger than any existing subsequence end,
# it extends the longest one found so far.
tails.append(num)
else:
# Otherwise, replace the first element >= num with 'num'.
# This maintains the smallest possible tail for that length.
idx = bisect.bisect_left(tails, num)
if idx < len(tails):
tails[idx] = num
return len(tails)
Edge Cases Handled
- Single Element: The loop runs once;
tailsbecomes[num], returns length 1. Correct. - All Duplicates (e.g., [7, 7]): First 7 appends to tails (
[7]). Second 7 triggers replacement at index 0 with itself or no change effectively since it’s not greater thantails[-1]. Length remains 1. Correct for strictly increasing. - Decreasing Sequence (e.g., [5,4]): First element
[5], second replaces 5 with 4 ([4]). Returns length 1. Correct.