#109 Medium Time O(n log n) Space O(n) Animated

Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence.

LeetCode ↗

Approach: Dynamic Programming (1D)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Find the length of the longest strictly increasing subsequence.

Constraints

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution — Dynamic Programming (1D)

O(n log n) O(n)

def lengthOfLIS(nums):
    LIS = [1] * len(nums)
    
    for i in range(len(nums) - 1, -1, -1):
        for j in range(i + 1, len(nums)):
            if nums[i] < nums[j]:
                LIS[i] = max(LIS[i], 1 + LIS[j])
                
    return max(LIS)

Word Break

Partition Equal Subset Sum

Longest Increasing Subsequence

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (1D)