LeetCode 300: Longest Increasing Subsequence

Problem Description

LeetCode Problem 300

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
• -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Difficulty: Medium

Tags: array, binary search, dynamic programming

Rating: 97.86%

Approach 1: Dynamic Programming

First, let’s look at the standard dynamic programming solution with O(n²) time complexity:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        dp = [1] * n  # dp[i] represents the length of LIS ending at index i
        
        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)

Complexity Analysis

• Time Complexity: $O(n²)$
• Space Complexity: $O(n)$

Approach 2: Binary Search

We can optimize this to O(n log n) using a binary search approach. The key insight is maintaining an array tails where tails[i] represents the smallest value that can end an increasing subsequence of length i+1.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []  # tails[i] = smallest value that can end a subsequence of length i+1
        
        for num in nums:
            # Binary search for the position to insert num
            left, right = 0, len(tails)
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            
            # If we should append num to extend the sequence
            if left == len(tails):
                tails.append(num)
            # Otherwise, replace the smallest number that is >= num
            else:
                tails[left] = num
        
        return len(tails)

How it Works

Let’s walk through an example with nums = [10,9,2,5,3,7,101,18]:

1. Initially tails = []
2. num = 10: tails = [10]
3. num = 9: tails = [9] (9 replaces 10 as it’s better for future numbers)
4. num = 2: tails = [2] (2 replaces 9)
5. num = 5: tails = [2,5] (start new subsequence)
6. num = 3: tails = [2,3] (3 replaces 5 as it’s better for future numbers)
7. num = 7: tails = [2,3,7] (start new subsequence)
8. num = 101: tails = [2,3,7,101] (start new subsequence)
9. num = 18: tails = [2,3,7,18] (18 replaces 101)

The length of tails array (4) is our answer.

Key Insights

1. The tails array is always sorted, which allows us to use binary search.
2. Each number either extends the sequence (appended to tails) or improves a potential future sequence (replaces a value in tails).
3. The length of tails equals the length of the longest increasing subsequence.
4. Note that tails array doesn’t necessarily represent an actual subsequence.

Complexity Analysis

• Time Complexity: $O(n log n)$
  • For each element, we perform a binary search taking O(log n) time
• Space Complexity: $O(n)$
  • We need to store the tails array

When to Use Which Approach

• Use the O(n²) DP solution when:

  • The input size is small (n < 100)
  • You need to reconstruct the actual subsequence
  • Code simplicity is prioritized

• Use the O(n log n) solution when:

  • The input size is large
  • Only the length is needed
  • Performance is critical
  • Memory usage isn’t a concern