Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Problem Understanding

A subsequence is derived by deleting some or no elements without changing the order.

Example: [10, 9, 2, 5, 3, 7, 101, 18]

One LIS: [2, 3, 7, 101]
Length: 4

Algorithm Strategy

We define dp[i] as the length of the LIS ending at index i.

Recurrence:
For each j < i, if nums[j] < nums[i], we can extend the subsequence ending at j.
dp[i] = max(dp[i], dp[j] + 1)

Base Case: dp[i] = 1 (subsequence of itself).

Interactive Visualization

Step 1 / 1

Initializing...

Custom Input

Watch how dp[i] checks all previous dp[j] values to find the maximum extensions.

Click 'Randomize' to test different arrays.

Dry Run

nums = [10, 9, 2, 5]

i	Val	Default	j (Comparing)	Extend?	New `dp[i]`
0	10	1	-	-	1
1	9	1	j=0 (10)	No (9<10)	1
2	2	1	j=0, j=1	No	1
3	5	1	j=2 (2)	Yes (5>2)	`dp[2]+1` = 2

Edge Cases & Common Mistakes

Details matter:

Strictly Increasing: Equal values ([2, 2, 2]) cannot extend. LIS is 1.
Single Element: If nums has 1 element, answer is 1.
Return Value: It's max(dp), not dp[n-1]. The LIS might end anywhere.

Solution

O(N^2) DP Solution. (Can be O(N log N) with Binary Search, but DP is core here).

1class Solution:
2    def lengthOfLIS(self, nums: List[int]) -> int:
3        n = len(nums)
4        dp = [1] * n
5        
6        for i in range(n):
7            for j in range(i):
8                if nums[i] > nums[j]:
9                    dp[i] = max(dp[i], dp[j] + 1)
10                    
11        return max(dp) if dp else 0

Complexity Analysis

Time Complexity: O(N^2). Nested loops.
Space Complexity: O(N) for DP array.