Longest Increasing Subsequence

Problem

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

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

Solution

Approach 1: Dynamic Programming O(n²)

The key insight is that for each element, the LIS ending at that element is 1 + the maximum LIS ending at any previous smaller element.

Implementation

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        n = len(nums)
        dp = [1] * n  # Each element is an LIS of length 1

        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)

Approach 2: Binary Search O(n log n)

import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []  # tails[i] = smallest tail of all LIS of length i+1

        for num in nums:
            # Find position where num should be inserted
            pos = bisect.bisect_left(tails, num)

            # If pos == len(tails), num is larger than all elements
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num

        return len(tails)

Approach 3: Binary Search (Manual Implementation)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []

        for num in nums:
            left, right = 0, len(tails)

            # Binary search for insertion position
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid

            # If num is larger than all elements, append it
            if left == len(tails):
                tails.append(num)
            else:
                tails[left] = num

        return len(tails)

Complexity Analysis

DP Approach:

Time Complexity: O(n²), where n is the length of array. For each element, we check all previous elements.
Space Complexity: O(n) for the dp array.

Binary Search Approach:

Time Complexity: O(n log n). For each element, we perform binary search which is O(log n).
Space Complexity: O(n) for the tails array.

Key Insights

DP Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i].
Subsequence vs Subarray: A subsequence doesn’t need to be contiguous, so we must check all previous elements.
Tails Array Invariant: In the binary search approach, tails[i] stores the smallest possible tail value for all increasing subsequences of length i+1.
Binary Search Optimization: Instead of checking all previous elements, we maintain a sorted array and use binary search to find where the current element fits.
Patience Sorting: The binary search approach is related to the patience sorting algorithm.
Greedy Choice: When building subsequences, we always want to keep the smallest possible tail value for each length, giving us more options for future elements.