300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

Summary

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

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Approach

First, I tried to use a min-heap. However, it did not work because this problem asks for the length of a strictly increasing subsequence.

A heap only keeps track of the minimum value. It does not preserve the information we need about subsequence order.

Instead, we can use binary search with patience sorting.

Function

Initialize:

• tails = []
• tails[i] stores the smallest possible tail value of an increasing subsequence of length i + 1.

For each number n in nums:

• Find the insertion position pos of n in tails.
• If pos is equal to len(tails), append n to tails.
• Otherwise, overwrite tails[pos] = n.

To find the position of n in tails, use binary search.

Return len(tails).

Example:

Input: nums = [10,9,2,5,3,7,101,18]

1. 10, tails=[10]
2. 9, tails=[9]
3. 2, tails=[2]
4. 5, tails=[2,5]
5. 3, tails=[2,3]
6. 7, tails=[2,3,7]
7. 101, tails=[2,3,7,101]
8. 18, tails=[2,3,7,18]

The length is 4.

Complexity

Time Complexity: O(N log N). We process each element once, and each binary search takes O(log N). Space Complexity: O(N) for tails.

Approach 2

DP.

Let dp[i] be the length of the longest increasing subsequence that ends at index i.

• If nums[i] > nums[j], then dp[i] = max(dp[i], dp[j] + 1).

Function

Initialization:

• dp = [1] * len(nums)

For each i in nums:

• For each j from 0 to i - 1:
• If nums[i] > nums[j], update dp[i] = max(dp[i], dp[j] + 1).

Return max(dp).

Complexity

Time Complexity: O(N^2). Space Complexity: O(N).