LeetCode 300 - Longest Increasing Subsequence
The problem asks us to find the length of the longest strictly increasing subsequence in an array of integers. A subsequence is formed by deleting zero or more elements from the array without changing the order of the remaining elements.
Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming
Solution
Problem Understanding
The problem asks us to find the length of the longest strictly increasing subsequence in an array of integers.
A subsequence is formed by deleting zero or more elements from the array without changing the order of the remaining elements. This is different from a subarray, which must remain contiguous. Because of this distinction, we are allowed to skip elements as long as the relative order stays the same.
The subsequence must also be strictly increasing. That means every next element must be greater than the previous one. Equal values are not allowed in the sequence.
For example, in the array [10,9,2,5,3,7,101,18], one valid increasing subsequence is [2,3,7,101]. Its length is 4, which is the maximum possible, so the answer is 4.
The input consists of:
- An integer array
nums - Array length between
1and2500 - Values can range from
-10^4to10^4
The output is a single integer representing the maximum length of any strictly increasing subsequence.
The constraints are important because they guide algorithm selection. Since n can be as large as 2500, an exponential brute-force solution would be far too slow. Even an O(n^2) dynamic programming solution is acceptable for this constraint size, but the follow-up specifically asks for an O(n log n) solution.
Several edge cases are important:
- Arrays with all identical values, such as
[7,7,7,7], should return1 - Arrays already strictly increasing should return the full length
- Arrays strictly decreasing should also return
1 - Negative numbers must be handled correctly
- Very short arrays, especially length
1, should work without special handling errors
Understanding the difference between subsequences and contiguous subarrays is the key conceptual challenge in this problem.
Approaches
Brute Force Approach
The brute-force solution explores every possible subsequence of the array and checks whether each subsequence is strictly increasing.
For an array of length n, every element can either be included or excluded, resulting in 2^n possible subsequences. For each subsequence, we would need to verify whether it is increasing and track the maximum valid length.
This approach is correct because it examines all possible subsequences, guaranteeing that the optimal one will eventually be found.
However, the time complexity is exponential, which becomes infeasible very quickly. Even for n = 50, the number of subsequences becomes enormous. Since the problem allows n = 2500, brute force is completely impractical.
Key Insight for the Optimal Solution
The important observation is that we do not need to store every subsequence explicitly.
Instead, we can maintain a structure that tracks the smallest possible tail value for increasing subsequences of different lengths.
Suppose we know:
- The smallest tail of an increasing subsequence of length
1 - The smallest tail of an increasing subsequence of length
2 - The smallest tail of an increasing subsequence of length
3 - And so on
A smaller tail is always better because it leaves more room for future elements to extend the subsequence.
This leads to the classic greedy plus binary search solution.
We maintain an array called tails where:
tails[i]stores the smallest possible ending value of an increasing subsequence of lengthi + 1
As we process each number:
- If the number is larger than all current tails, we extend the subsequence
- Otherwise, we replace the first tail greater than or equal to the number
Binary search allows us to find the replacement position efficiently in O(log n) time.
The length of tails at the end equals the length of the longest increasing subsequence.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) |
O(n) |
Generates all possible subsequences |
| Optimal | O(n log n) |
O(n) |
Uses greedy strategy with binary search |
Algorithm Walkthrough
- Initialize an empty array called
tails.
The purpose of tails is to maintain the smallest possible tail value for increasing subsequences of different lengths.
For example:
tails[0]represents the smallest tail for subsequences of length1tails[1]represents the smallest tail for subsequences of length2
Smaller tail values are preferred because they provide more opportunities for extension later.
2. Iterate through each number in nums.
We process the array left to right because subsequences must preserve original ordering. 3. Use binary search to find the insertion position.
For the current number:
- Find the leftmost position in
tailswhere the value is greater than or equal to the current number - This position tells us which subsequence length can be improved
Binary search is appropriate because tails is always maintained in sorted order.
4. Update tails.
There are two cases:
- If the current number is larger than all existing tails, append it to
tails - Otherwise, replace the existing tail at the binary search position
Replacing does not reduce the LIS length. Instead, it improves the future potential by creating a smaller tail. 5. Continue until all elements are processed.
The final size of tails represents the length of the longest increasing subsequence.
Why it works
The key invariant is that tails[i] always stores the smallest possible ending value for an increasing subsequence of length i + 1.
If we can make a subsequence end with a smaller number, that subsequence becomes easier to extend later. Therefore, replacing larger tails with smaller ones is always safe and beneficial.
Although tails itself may not represent an actual subsequence from the array, its length always matches the length of the longest increasing subsequence discovered so far.
Python Solution
from typing import List
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for num in nums:
position = bisect.bisect_left(tails, num)
if position == len(tails):
tails.append(num)
else:
tails[position] = num
return len(tails)
The implementation begins by creating the tails array, which stores the smallest possible tail values for increasing subsequences of various lengths.
For each number in the input array, we use bisect_left to perform binary search. This finds the first index where the current number can be inserted while preserving sorted order.
If the insertion position equals the current length of tails, the number extends the longest subsequence found so far, so we append it.
Otherwise, we replace the existing value at that position. This replacement improves the subsequence by creating a smaller tail value without changing the subsequence length.
Finally, the length of tails is returned because it equals the length of the longest increasing subsequence.
Go Solution
func lengthOfLIS(nums []int) int {
tails := []int{}
for _, num := range nums {
left := 0
right := len(tails)
for left < right {
mid := left + (right-left)/2
if tails[mid] < num {
left = mid + 1
} else {
right = mid
}
}
if left == len(tails) {
tails = append(tails, num)
} else {
tails[left] = num
}
}
return len(tails)
}
The Go implementation follows the same algorithmic logic as the Python version. Since Go does not provide a direct equivalent of Python's bisect_left for slices, we implement binary search manually.
The tails slice grows dynamically as longer subsequences are discovered. Replacement operations modify existing indices directly.
There are no integer overflow concerns because the values remain well within Go's integer range. Empty and single-element arrays are naturally handled without special-case logic.
Worked Examples
Example 1
Input:
nums = [10,9,2,5,3,7,101,18]
| Step | Current Number | tails Before | Action | tails After |
|---|---|---|---|---|
| 1 | 10 | [] |
Append 10 | [10] |
| 2 | 9 | [10] |
Replace 10 with 9 | [9] |
| 3 | 2 | [9] |
Replace 9 with 2 | [2] |
| 4 | 5 | [2] |
Append 5 | [2,5] |
| 5 | 3 | [2,5] |
Replace 5 with 3 | [2,3] |
| 6 | 7 | [2,3] |
Append 7 | [2,3,7] |
| 7 | 101 | [2,3,7] |
Append 101 | [2,3,7,101] |
| 8 | 18 | [2,3,7,101] |
Replace 101 with 18 | [2,3,7,18] |
Final answer:
4
Even though [2,3,7,18] is not the original LIS shown in the example, its length is still correct.
Example 2
Input:
nums = [0,1,0,3,2,3]
| Step | Current Number | tails Before | tails After |
|---|---|---|---|
| 1 | 0 | [] |
[0] |
| 2 | 1 | [0] |
[0,1] |
| 3 | 0 | [0,1] |
[0,1] |
| 4 | 3 | [0,1] |
[0,1,3] |
| 5 | 2 | [0,1,3] |
[0,1,2] |
| 6 | 3 | [0,1,2] |
[0,1,2,3] |
Final answer:
4
Example 3
Input:
nums = [7,7,7,7,7,7,7]
| Step | Current Number | tails Before | tails After |
|---|---|---|---|
| 1 | 7 | [] |
[7] |
| 2 | 7 | [7] |
[7] |
| 3 | 7 | [7] |
[7] |
| 4 | 7 | [7] |
[7] |
| 5 | 7 | [7] |
[7] |
| 6 | 7 | [7] |
[7] |
| 7 | 7 | [7] |
[7] |
Final answer:
1
Since the subsequence must be strictly increasing, duplicate values cannot extend the sequence.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) |
Each element performs a binary search on tails |
| Space | O(n) |
The tails array can grow to size n |
The algorithm processes each number exactly once. For every element, we perform binary search on the tails array, which takes O(log n) time.
Since there are n elements total, the complete runtime becomes O(n log n).
The tails array may grow to the full array size in the case of an already increasing sequence, resulting in O(n) extra space usage.
Test Cases
from typing import List
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for num in nums:
position = bisect.bisect_left(tails, num)
if position == len(tails):
tails.append(num)
else:
tails[position] = num
return len(tails)
solution = Solution()
assert solution.lengthOfLIS([10,9,2,5,3,7,101,18]) == 4 # standard example
assert solution.lengthOfLIS([0,1,0,3,2,3]) == 4 # multiple valid LIS
assert solution.lengthOfLIS([7,7,7,7,7,7,7]) == 1 # all duplicates
assert solution.lengthOfLIS([1]) == 1 # single element
assert solution.lengthOfLIS([1,2,3,4,5]) == 5 # already increasing
assert solution.lengthOfLIS([5,4,3,2,1]) == 1 # strictly decreasing
assert solution.lengthOfLIS([2,2,2,2]) == 1 # repeated equal values
assert solution.lengthOfLIS([-1,-2,-3,-4]) == 1 # negative decreasing
assert solution.lengthOfLIS([-4,-3,-2,-1]) == 4 # negative increasing
assert solution.lengthOfLIS([4,10,4,3,8,9]) == 3 # replacement behavior
assert solution.lengthOfLIS([3,5,6,2,5,4,19,5,6,7,12]) == 6 # complex case
| Test | Why |
|---|---|
[10,9,2,5,3,7,101,18] |
Standard example with replacements |
[0,1,0,3,2,3] |
Tests multiple subsequence paths |
[7,7,7,7,7,7,7] |
Ensures duplicates do not extend LIS |
[1] |
Smallest valid input |
[1,2,3,4,5] |
Entire array is LIS |
[5,4,3,2,1] |
Worst-case decreasing input |
[2,2,2,2] |
Strictly increasing requirement |
[-1,-2,-3,-4] |
Negative decreasing sequence |
[-4,-3,-2,-1] |
Negative increasing sequence |
[4,10,4,3,8,9] |
Validates tail replacement logic |
[3,5,6,2,5,4,19,5,6,7,12] |
Complex mixed ordering |
Edge Cases
One important edge case is an array where all elements are identical, such as [7,7,7,7]. A common bug is accidentally treating non-decreasing sequences as increasing sequences. Since the problem requires strictly increasing order, duplicates cannot extend the subsequence. The implementation correctly handles this by using bisect_left, which replaces existing values instead of appending duplicates.
Another critical case is a strictly decreasing array like [5,4,3,2,1]. In this scenario, every new element replaces the first position in tails, and the array never grows beyond length 1. This ensures the algorithm correctly returns 1 instead of incorrectly counting multiple elements.
A third important case is an already increasing array such as [1,2,3,4,5]. Here, every element is larger than the previous tails, so every number gets appended. The algorithm correctly grows tails to the full array length, producing the optimal answer.
Negative values also deserve attention because comparisons must work independently of sign. Arrays like [-4,-3,-2,-1] behave exactly the same as positive increasing arrays. Since the algorithm relies only on ordering comparisons, it naturally handles negative integers without additional logic.
Finally, very small inputs such as a single-element array can expose initialization bugs in some implementations. This solution avoids special-case code entirely because the tails array starts empty and grows naturally during iteration.