300. Longest Increasing Subsequence

MediumLeetCode

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

How to solve the problem

• Binary Search with Greedy

# Approach 1: Binary Search with Greedy
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        g = []  # g[i]: the smallest tail of all increasing subsequences of length i+1
        for x in nums:
            j = bisect_left(g, x)  # find insertion point for x to keep g sorted
            if j == len(g):
                g.append(x)  # extend the sequence
            else:
                g[j] = x  # replace to maintain the smallest possible tail
        return len(g)  # length of LIS

Complexity

• Time complexity: O(n * log n)
• Space complexity: O(n)