Longest Increasing Subsequence
Problem Statement
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.
Constraints:
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4
Input Format:
- An integer array nums
Output Format:
- An integer representing the length of the longest increasing subsequence
Examples:
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
Explanation:
The longest increasing subsequence is [0,1,2,3], therefore the length is 4.
Example 3:
Input:
nums = [7,7,7,7,7,7,7]
Output:
1
Explanation:
The longest increasing subsequence is [7], therefore the length is 1.
Solutions
Dynamic Programming Approach
For each position i, find the longest increasing subsequence ending at that position by checking all previous positions j. If nums[i] > nums[j], we can extend the subsequence ending at j.
Binary Search Approach
Maintain a sorted array of potential values in the subsequence. For each element, find its position in this array using binary search and update accordingly.
Algorithm Walkthrough
Example input: nums = [10,9,2,5,3,7,101,18]
Step-by-step execution:
- Dynamic Programming Approach:
- Initialize dp array: [1, 1, 1, 1, 1, 1, 1, 1]
- i=1, nums[1]=9: No j where nums[j] < nums[1], dp stays [1, 1, 1, 1, 1, 1, 1, 1]
- i=2, nums[2]=2: No j where nums[j] < nums[2], dp stays [1, 1, 1, 1, 1, 1, 1, 1]
- i=3, nums[3]=5: For j=2, nums[2]=2 < nums[3]=5, dp[3] = max(dp[3], dp[2]+1) = max(1, 1+1) = 2, dp becomes [1, 1, 1, 2, 1, 1, 1, 1]
- i=4, nums[4]=3: For j=2, nums[2]=2 < nums[4]=3, dp[4] = max(dp[4], dp[2]+1) = max(1, 1+1) = 2, dp becomes [1, 1, 1, 2, 2, 1, 1, 1]
- i=5, nums[5]=7: For j=2, nums[2]=2 < nums[5]=7, dp[5] = max(dp[5], dp[2]+1) = max(1, 1+1) = 2
- For j=3, nums[3]=5 < nums[5]=7, dp[5] = max(dp[5], dp[3]+1) = max(2, 2+1) = 3
- For j=4, nums[4]=3 < nums[5]=7, dp[5] = max(dp[5], dp[4]+1) = max(3, 2+1) = 3, dp becomes [1, 1, 1, 2, 2, 3, 1, 1]
- i=6, nums[6]=101: For all j<6, nums[j] < nums[6], max is at j=5 with dp[5]=3, dp[6] = dp[5]+1 = 4, dp becomes [1, 1, 1, 2, 2, 3, 4, 1]
- i=7, nums[7]=18: For j=2,3,4,5, nums[j] < nums[7], max is at j=5 with dp[5]=3, dp[7] = dp[5]+1 = 4, dp becomes [1, 1, 1, 2, 2, 3, 4, 4]
- The final dp array is [1, 1, 1, 2, 2, 3, 4, 4], and the maximum value is 4, which is the length of the LIS.
- Binary Search Approach:
- Initialize tails array: []
- For num=10: Insert into tails at position 0, tails = [10]
- For num=9: Since 9 < 10, replace at position 0, tails = [9]
- For num=2: Since 2 < 9, replace at position 0, tails = [2]
- For num=5: Since 5 > 2, insert at position 1, tails = [2, 5]
- For num=3: Since 2 < 3 < 5, replace at position 1, tails = [2, 3]
- For num=7: Since 7 > 3, insert at position 2, tails = [2, 3, 7]
- For num=101: Since 101 > 7, insert at position 3, tails = [2, 3, 7, 101]
- For num=18: Since 7 < 18 < 101, replace at position 3, tails = [2, 3, 7, 18]
- The length of the tails array is 4, which is the length of the LIS.
Hints
Hint 1
Hint 2
Hint 3
Hint 4
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize either the dynamic programming table or the growth of the tails array in the binary search approach.
Key visualization elements:
- current element
- dp array state
- binary search process
Implementation Notes
This problem showcases the power of both dynamic programming and binary search techniques. The DP approach is intuitive but requires quadratic time, while the binary search approach achieves the same result in linearithmic time at the cost of being more conceptually challenging.