Longest Increasing Subsequence
I share my learnings here. Thanks for reading.
Problem
Given an integer array nums, return the length of the longest strictly increasing subsequence. (link)
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
This approach is similar to deciding whether to include or exclude an element. It depends on the next element. Consider the options of including or excluding the element and proceed accordingly.
Recursion
Time - O(2^n)
Space - O(n)
class Solution {
private int maxLength(int i, int ahead, int[] nums){
if(i<0) return 0;
if(nums[i]<ahead) {
int take = 1 + maxLength(i-1, nums[i], nums);
int notTake = maxLength(i-1, ahead, nums);
return Math.max(take, notTake);
}
return maxLength(i-1, ahead, nums);
}
public int lengthOfLIS(int[] nums) {
return maxLength(nums.length-1, Integer.MAX_VALUE, nums);
}
}
Memoization
Time - O(nxn)
Space - O(nxn) + O(n)
class Solution {
private int maxLength(int i, int aheadIndex, int[] nums, int[][] dp){
if(i<0) return 0;
if(dp[i][aheadIndex]!=-1) return dp[i][aheadIndex];
int ahead = aheadIndex<nums.length ? nums[aheadIndex] : Integer.MAX_VALUE;
if(nums[i]<ahead){
int take = 1 + maxLength(i-1, i, nums, dp);
int notTake = maxLength(i-1, aheadIndex, nums, dp);
return dp[i][aheadIndex] = Math.max(take, notTake);
}
return dp[i][aheadIndex] = maxLength(i-1, aheadIndex, nums, dp);
}
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[][] dp = new int[n+1][n+1];
for(int[] row : dp){
Arrays.fill(row, -1);
}
return maxLength(n-1, n, nums, dp);
}
}
Tabulation
Time - O(nxn)
Space - O(nxn)
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[][] dp = new int[n+1][n+1];
for(int i=1; i<n+1; i++){
for(int aheadIndex=i; aheadIndex < n+1; aheadIndex++){
int ahead = aheadIndex < n ? nums[aheadIndex] : Integer.MAX_VALUE;
if(nums[i-1] < ahead){
int take = 1 + dp[i-1][i-1];
int notTake = dp[i-1][aheadIndex];
dp[i][aheadIndex] = Math.max(take, notTake);
}
else{
dp[i][aheadIndex] = dp[i-1][aheadIndex];
}
}
}
return dp[n][n];
}
}
Space Optimization
Time - O(nxn)
Space - O(n)
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] prev = new int[n+1];
for(int i=1; i<n+1; i++){
int[] curr = new int[n+1];
for(int aheadIndex=i; aheadIndex < n+1; aheadIndex++){
int ahead = aheadIndex < n ? nums[aheadIndex] : Integer.MAX_VALUE;
if(nums[i-1] < ahead){
int take = 1 + prev[i-1];
int notTake = prev[aheadIndex];
curr[aheadIndex] = Math.max(take, notTake);
}
else{
curr[aheadIndex] = prev[aheadIndex];
}
}
prev = curr;
}
return prev[n];
}
}
Approach 2
We will use dynamic programming with a different approach. Imagine we are at the ith element. The dp value at position i will be the maximum of any element’s dp before i. Essentially, this maximum is max(dp[0], dp[1],…,dp[j]…,dp[i-1]) + 1 is the dp[i]
Note: We use a global max to keep track of the highest value recorded so far.
Time - O(nxn)
Space - O(n)
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ans = 1;
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[i], 1+dp[j]);
ans = Math.max(ans, dp[i]);
}
}
}
return ans;
}
}
Print LIS
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int[] parent = new int[n];
Arrays.fill(dp, 1);
int ans = 1;
int lastChildIndex = 0;
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
if(nums[j] < nums[i]){
if(dp[i]< 1+dp[j]){
dp[i] = 1 + dp[j];
parent[i] = j;
}
if(ans<dp[i]){
ans = dp[i];
lastChildIndex = i;
}
}
}
}
int[] arr = new int[ans];
int index = ans-1;
while(parent[lastChildIndex] != lastChildIndex){
arr[index] = nums[lastChildIndex];
lastChildIndex = parent[lastChildIndex];
index-=1;
}
for(int val : arr){
System.out.print(" "+val);
}
return ans;
}
}
Approach 3 (Binary Search)
[1, 7, 8, 4, 5, 6, -1, 9]
--1---
[1]
--7---
[1, 7]
--8---
[1, 7, 8]
--4---
[1, 7, 8]
[1, 4]
--5---
[1, 7, 8]
[1, 4, 5]
--6---
[1, 7, 8]
[1, 4, 5, 6]
--(-1)---
[1, 7, 8]
[1, 4, 5, 6]
[-1]
--9---
[1, 7, 8, 9]
[1, 4, 5, 6, 9]
[-1, 9]
Thinking
We build all subsequences and focus on increasing ones.
Maintaining multiple subsequences is inefficient since we only need the longest increasing subsequence.
We optimize by keeping only one subsequence and focus on its length.
If a new number is greater than the last element, we add it.
If a new number is smaller, we replace an element to maintain a possible subsequence.
This replacement signifies a potential subsequence but not necessarily the actual one.
We keep the lowest tail to ensure the longest increasing length.
To find the longest increasing subsequence efficiently follow these steps:
Initialize an Empty List:
- Start with an empty list that will store the smallest possible tail for all increasing subsequences of different lengths.
Iterate Through Each Number:
- For each number in the array, determine its position in the current list using binary search.
Binary Search Logic (lower bound):
If the number is greater than the last element in the list, append it to the list. This extends the longest subsequence found so far.
If the number is smaller or equal, find the position where it can replace an existing element. This helps in maintaining the smallest possible tail for subsequences of that length.
Maintain the Smallest Tail:
- By replacing elements, ensure that the list always contains the smallest possible tail for subsequences of each length. This allows for potential longer subsequences as the iteration continues.
Result:
- The length of the list at the end of the iteration represents the length of the longest increasing subsequence.
Example Walkthrough:
Start with an empty list:
[]Process each number:
1: Add to list →
[1]7: Add to list →
[1, 7]8: Add to list →
[1, 7, 8]4: Replace 7 with 4 →
[1, 4, 8]5: Replace 8 with 5 →
[1, 4, 5]6: Add to list →
[1, 4, 5, 6]-1: Replace 1 with -1 →
[-1, 4, 5, 6]9: Add to list →
[-1, 4, 5, 6, 9]
Final List:
[-1, 4, 5, 6, 9](Length is 5)
By following these steps, you efficiently find the longest increasing subsequence using minimal space and time.
Time - O(n logn)
Space - O(n)
class Solution {
private int getLowerBound(int x, List<Integer> arr){
int low = 0;
int high = arr.size()-1;
int ans = 0;
while(low <= high){
int mid = (low + high)/2;
if(x <= arr.get(mid)){
ans = mid;
high = mid-1;
}
else{
low = mid + 1;
}
}
return ans;
}
public int lengthOfLIS(int[] nums) {
int n = nums.length;
List<Integer> ans = new ArrayList<>();
ans.add(nums[0]);
int top = 0; //optional
for(int i=1; i<n; i++){
if(ans.get(top)<nums[i]){
ans.add(nums[i]);
top+=1;
}
else{
int index = getLowerBound(nums[i], ans);
ans.set(index, nums[i]);
}
}
return ans.size();
}
}