18. Longest Increasing Subsequence
Problem Statement
Given an integer array nums
, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Solution
import bisect
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
# This list will store the smallest tail of all increasing subsequences
# with length i+1 in tails[i].
tails = []
for num in nums:
# Find the first position where num can be inserted to maintain order
i = bisect.bisect_left(tails, num)
if i == len(tails):
# If num is greater than all elements in tails, extend the subsequence
tails.append(num)
else:
# Replace the tail of an existing subsequence with a smaller number
# This allows for potentially longer subsequences later on
tails[i] = num
return len(tails)
Explanation
This problem can be solved with a clever approach that uses both dynamic programming and binary search, resulting in an O(n log n) time complexity.
The core idea is to maintain a list called tails
. This list stores the smallest tail of all increasing subsequences with a certain length. tails[i]
will be the smallest tail of an increasing subsequence of length i+1
.
Let's trace nums = [10, 9, 2, 5, 3, 7, 101, 18]
:
num = 10
:tails
is[]
.i=0
.tails
becomes[10]
.num = 9
:tails
is[10]
.i=0
.tails
becomes[9]
(replace 10).num = 2
:tails
is[9]
.i=0
.tails
becomes[2]
(replace 9).num = 5
:tails
is[2]
.i=1
.tails
becomes[2, 5]
.num = 3
:tails
is[2, 5]
.i=1
.tails
becomes[2, 3]
(replace 5).num = 7
:tails
is[2, 3]
.i=2
.tails
becomes[2, 3, 7]
.num = 101
:tails
is[2, 3, 7]
.i=3
.tails
becomes[2, 3, 7, 101]
.num = 18
:tails
is[2, 3, 7, 101]
.i=3
.tails
becomes[2, 3, 7, 18]
(replace 101).
The final tails
list is [2, 3, 7, 18]
. The length of this list, 4, is the length of the longest increasing subsequence.
We use bisect.bisect_left
to perform the binary search efficiently. This finds the insertion point for num
in tails
to keep it sorted. This is the key to the O(n log n) performance.
The space complexity is O(n) for the tails
list.