MediumBlind75ArrayDPBinary Search
Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Examples
Input
nums = [10,9,2,5,3,7,101,18]
Output
4
The longest increasing subsequence is [2,3,7,101], length 4.
Input
nums = [0,1,0,3,2,3]
Output
4
The longest increasing subsequence is [0,1,2,3], length 4.
Constraints
- •
1 <= nums.length <= 2500 - •
-10^4 <= nums[i] <= 10^4
Approaches
Generate all subsequences and check which are increasing.
CodeT: O(2^n) | S: O(n)
def length_of_lis(nums):
def helper(start, prev):
if start == len(nums):
return 0
take = 0
if nums[start] > prev:
take = 1 + helper(start + 1, nums[start])
skip = helper(start + 1, prev)
return max(take, skip)
return helper(0, float('-inf'))Use DP where dp[i] is the length of LIS ending at index i.
CodeT: O(n^2) | S: O(n)
def length_of_lis(nums):
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Maintain a sorted array of potential LIS ends.
Diagram
nums = [10,9,2,5,3,7,101,18]
tails: [10] -> [9] -> [2] -> [2,5] -> [2,3] -> [2,3,7] -> [2,3,7,101] -> [2,3,7,18]
Length: 4
CodeT: O(n log n) | S: O(n)
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)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force - All Subsequences | O(2^n) | O(n) | Generate all subsequences and check which are increasing. |
| DP - O(n^2) | O(n^2) | O(n) | Use DP where dp[i] is the length of LIS ending at index i. |
| Binary Search - O(n log n) | O(n log n) | O(n) | Maintain a sorted array of potential LIS ends. |
Brute Force - All Subsequences
T: O(2^n)S: O(n)
Generate all subsequences and check which are increasing.
DP - O(n^2)
T: O(n^2)S: O(n)
Use DP where dp[i] is the length of LIS ending at index i.
Binary Search - O(n log n)
T: O(n log n)S: O(n)
Maintain a sorted array of potential LIS ends.
Common Mistakes
Confusing subsequence with substring (subsequence is non-contiguous)
Using a set which loses order information
Not handling the case where the array is strictly decreasing