Longest Increasing Subsequence

Problem Statement

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

A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7].

The task is to find the length of the longest subsequence in which every element is greater than the previous one.

LeetCode:

https://leetcode.com/problems/longest-increasing-subsequence/

Constraints:

1 <= nums.length <= 10^5
-10^6 <= nums[i] <= 10^6

Array Size: 1 ≤ nums.length ≤ 10^5
1. The array nums will have atleast 1 element and at most 1,00,000 elements.
2. With up to 10^5 elements, an O(n^2) solution 10^10 operations will give the TLE.
3. You will generally need O(n log n) algorithm to run within time limits.
Value Range: -10^6 ≤ nums[i] ≤ 10^6
1. Every element in the array is an integer between -10,00,000 and +10,00,000, inclusive.
2. An int (32 bit) comfortably holds values up to +_(2*10^9), so nums[i] fits without overflow.
3. If you ever do arithmetic that could exceed ~1*10^9, you would switch to long long.

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], and its 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], and its length is 4.

Different Approaches

1️⃣ Brute Force Approach (Recursive) (TLE)

A naive approach to solve this problem is to generate all the possible subsequences (using Power Set or Recursion method), check if the subsequence is increasing and then store the longest among them. Clearly, this approach will not be a useful approach for the given problem as it will end up taking O(2^N), where N is the number of elements in the given array, i.e., exponential time complexity.

Intuition:

Try all combinations by either picking or skipping each element.

Approach:

Steps to form the recursive solution:

Express the problem in terms of indices: Let us define a function f(ind) that represents the length of the Longest Increasing Subsequence (LIS) starting from ind. Ultimately, the result will be the f(0).
1. The problem is now reduced to calculating f(0).
Try all possible choices for each index: At each index ind, we consider whether the current element should extend a previous subsequence or not. This gives an idea to introduce another parameter prev_ind in the function such that the following two possibilities arise:
1. Not Take case (If arr[prev_ind] >= arr[ind]): In such case, the current element cannot be taken into consideration because the goal is to form an increasing subsequence. Since the element is not taken, the prev_ind remains the same and the call simply jumps to the next index i.e., f(ind+1, prev_ind).
2. Take case (If arr[prev_ind] < arr[ind]): In such case, the current element can be added to the previously considered subsequence (ending at prev_ind) thus increasing the length of LIS by 1 and the call simply jumps to func(ind + 1, ind).
  1. Note that, the prev_ind is updated to ind, as now the ind becomes the last selected index for the further subsequence.
3. Initial case when the subsequence is empty: Initially, when the function call begins, there is no element chosen for the subsequence. To mark this, prev_ind can be set as -1 representing that the current element will be the first element that will be taken into consideration.
  1. Hence, to get the answer, the initial function call must be f(0, -1).
Return the longest length of LIS found: After the take and notTake calls, the longest length of the subsequence found can be returned as the answer to the current function call.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

/* Function to return the length of LIS starting from 
index i with the element prev_ind element refers to
the previously selected element in the subsequence*/
func(int i, int prev_ind, int arr[]) {
    
    // Not Take case
    int notTake = func(i+1, prev_ind, arr);
    
    // Take case
    int take = 0;
    
    // If no element is chosen till now
    if(prev_ind == -1)
        take = func(i+1, i, arr) + 1;
    
    /* Else the current element can be 
    taken if it is strictly increasing */
    else if(arr[i] > arr[prev_ind])
        take = func(i+1, i, arr) + 1;
    
    // Return the maximum length obtained from both cases
    return max(take, notTake);
}

Base cases:

When the function call reaches the last index, the base case will be called and there will be two cases:
- Take case: If the last index element is greater than the prev_ind element in the subsequnce or if the last index element is the first element in the subsequence, it can be taken in the subsequence and 1 can be returned.
- Not Take case: Otherwise, the last index element can not be considered and 0 can be returned.

Code:

class Solution {
public:
    // Recursive function to compute LIS starting from index i
    // prevIndex stores the index of the previously included element
    int solve(int i, int prevIndex, vector<int>& nums) {
        // Base case: if we reach the end of the array
        if (i == nums.size()) return 0;

        int take = 0;

        // Option 1: Take current element if it's greater than previous
        if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
            // Include current element and move to next index
            take = 1 + solve(i + 1, i, nums);
        }

        // Option 2: Skip current element and move to next
        int skip = solve(i + 1, prevIndex, nums);

        // Return the maximum of including or skipping the current element
        return max(take, skip);
    }

    // Main function to start recursion
    int lengthOfLIS(vector<int>& nums) {
        return solve(0, -1, nums); // Start from index 0 with no previous element selected
    }
};

OR:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Helper function to find the length of LIS
    int func(int i, int prevInd, vector<int> &arr) {
        
        // base case
        if(i == arr.size() - 1) {
            if(prevInd == -1 || arr[prevInd] < arr[i]) return 1;
            return 0;
        }
        
        // Not Take case
        int notTake = func(i+1, prevInd, arr);
        
        int take = 0; // Take case
        
        // If no element is chosen till now
        if(prevInd == -1)
            take = func(i+1, i, arr) + 1;
        
        /* Else the current element can be 
        taken if it is strictly increasing */
        else if(arr[i] > arr[prevInd])
            take = func(i+1, i, arr) + 1;
        
        // Return the maximum length obtained from both cases
        return max(take, notTake);
    }
    
public:
    /* Function to find the longest increasing 
    subsequence in the given array */
    int LIS(vector<int>& nums) {
        return func(0, -1, nums);
    }    
};


int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    // Creating an object of Solution class
    Solution sol;
    int lengthOfLIS = sol.LIS(nums);
    
    cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
    
    return 0;
}

Complexity Analysis:

Time Complexity:O(2^n)
- Each element has 2 choice: take or skip.
- In each function call, two recursive calls are made (take or not take) resulting in an exponential time complexity.
Space Complexity:O(n)
- Maximum recursion depth in worst case where we take all elements.

2️⃣ Memoization

If you draw the recursion tree, you will see that there are overlapping subproblems. Hence the DP approach can be applied to the recursive solution to optimise it.

Steps to convert the recursive solution to the Memoization solution:

Declare a dp array of size n*n: There are two states of dp which are:
1. ind: which can go from 0 to n-1, requiring a total of n indices.
2. prev_ind: which can go from -1 to n-2, requiring a total of (n-2 -(-1) +1) or n states.
3. Important:
  1. Note that there is no index as -1, hence, to store the state (prev_ind = -1), it is required to do a co-ordinate shift. We can map the -1 index to 0, 0 index to 1, and so on.…
  2. Hence, a 2D dp array is needed where dp[ind][prev_ind+1] stores the result of the function call func(ind, prev_ind). The dp array stores the calculations of subproblems hence it is initialized with -1, to indicate that no subproblem has been solved yet.
While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
Store the value of subproblem: Whenever, a subproblem is encountered and it is not solved yet (the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array before returning the function call.

Note

Note that submitting the following code will throw a runtime error because of the tight constraints set for the problem. N can go upto 10^5 and declaring a 2D dp of size N*N will require 10^10 space causing Memory Limit Exceeded resulting in runtime error.

Code:

class Solution {
public:

    // Recursive function to compute LIS starting from 'index'
    // prevInd: index of the previous element taken in the subsequence
    // dp: memoization table to store previously computed results
    int recursive(int index, int prevInd, vector<int>& nums, vector<vector<int>>& dp) {
        
        // Base Case: if we've gone past the last element
        if (index >= nums.size()) {
            return 0;  // No more elements to include
        }

        // Memoization check: return the result if already computed
        if (dp[index][prevInd + 1] != -1) {
            return dp[index][prevInd + 1];
        }

        // Choice 1: Take the current element if it's greater than the previous one
        int take = 0;
        if (prevInd == -1 || nums[prevInd] < nums[index]) {
            take = 1 + recursive(index + 1, index, nums, dp);
        }

        // Choice 2: Skip the current element
        int skip = recursive(index + 1, prevInd, nums, dp);

        // Store the maximum of both choices in the dp table and return
        return dp[index][prevInd + 1] = max(take, skip);
    }

    // Main function to calculate LIS length
    int LIS(vector<int>& nums) {
        int n = nums.size();  // Get the size of the input array

        // Initialize a 2D dp table with -1
        // dp[i][j] means LIS starting from index i, where last element taken is at index j-1
        // (we use prevInd+1 indexing to handle prevInd == -1 case)
        vector<vector<int>> dp(n, vector<int>(n + 1, -1));

        // Start recursion from index 0 and with no previous index (-1)
        return recursive(0, -1, nums, dp); 
    }   
};

Complexity Analysis:

Time Complexity:O(N^2), where N is the size of the array
- Because there will be a total of N*N states for which the function will be called.
Space Complexity:O(N^2), because of the 2D dp array created taking O(N^2) space and O(N) recursive stack space.

3️⃣ Binary Search (Lazy Sorting)

Intuition:

To solve the problem efficiently, a greedy approach can be used. Instead of creating new subsequences every time, we can store the length of LIS as we process elements one by one in the array.

Understanding:

Consider the following array: nums = [1, 5, 7, 2, 3]
Let us try to find the length of Longest Increase Subsequence step by step taking a temporary array (initially temp is empty):

At i = 0: The element at index 0 (1) can be added to temp as it is the first element being added. Thus,
temp = [1]
At i = 1: The element at index 1 (5) can be added to the subsequence as it is greater than the last element in temp, i.e., Since 5 > 1,
temp = [1, 5]
At i = 2: The element at index 2 (7) can be added to the subsequence as it is greater than the last element in temp, i.e., Since 7 > 5,
temp = [1, 5, 7]
At i = 3: The element at index 3 is 2 which is not greater than the last element, i.e., 2 ≯ 7. Now we cannot add it to the back of the temp array to form an increasing subsequence. Instead, we must find its correct index at which it can be placed in the current subsequence.
This gives an idea of using Binary Search to find the index in the sorted temp array where the current element can be placed.
As per the current example, the element 2 must be stored in the temp and the correct index where it will be placed is index 1. Hence, the element at index 1 in the temp array is replaced with 2. Thus,
temp = [1, 2, 7]
Note that temp array does not explicitly store the Longest Increasing Subsequence. Instead, the length of temp tells us about the length of Longest Increasing Subsequence seen till the current index.
At i = 4: The element at index 4 is 3 which is not greater than the last element, i.e., 3 ≯ 7. Now we cannot add it to the back of the temp array to form an increasing subsequence. Instead, we must find its correct index at which it can be placed in the current subsequence.
As per the current example, the element 3 must be stored in the temp and the correct index where it will be placed is index 2. Hence, the element at index 2 in the temp array is replaced with 3. Thus,
temp = [1, 2, 3]

Role of Binary Search:

As we process each number in the input array:

If the current number is greater than the last number in temp: The LIS can be extended by adding the current number to the end of temp.
If the current number is smaller or equal to some number in temp: Replace the smallest number in temp that is greater than or equal to the current number. This ensures that temp remains as small as possible, leaving room for future elements to extend the sequence.

Now, in order to efficiently find where to place or replace the current number in temp, we use binary search (Lower Bound functionality).

Approach:

Maintain a temporary list to represent the smallest possible increasing subsequence formed so far.
Iterate through each element in the input array:
1. If the current element is greater than the last element of the temporary list, append it to extend the subsequence.
2. Otherwise, use binary search to find the position in the temporary list where the current element should replace an element to keep the subsequence valid and minimal.
The size of the temporary list at the end of the iteration represents the length of the longest increasing subsequence.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the longest increasing 
    subsequence in the given array */
    int LIS(vector<int>& nums) {
        int n = nums.size();
        
        vector<int> temp;
        temp.push_back(nums[0]);
        
        // Iterate on the elements of the array
        for(int i=1; i < n; i++) {
            
            // If the current element can be added to the subsequence
            if(nums[i] > temp.back()) 
                temp.push_back(nums[i]); 
                
            // Otherwise
            else {
                // Index at which the current element must be placed
                int ind = lower_bound(temp.begin(), temp.end(), nums[i]) -
                          temp.begin();
                          
                // Place the current element in the subsequence
                temp[ind] = nums[i];
            }    
            
        }
        
        // Return the length of temporary subsequence created so far
        return temp.size();
    }    
};


int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    // Creating an object of Solution class
    Solution sol;
    int lengthOfLIS = sol.LIS(nums);
    
    cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
    
    return 0;
}

Complexity Analysis:

Time Complexity:O(N*logN), where N is the size of the given array
- Since the code leverages the Lower Bound function (implemented using binary search) it results is O(N*logN) complexity.
Space Complexity:O(N), to store the elements in the temp array.

4️⃣ Tabulation (Bottom Up) Approach

Intuition:

dp[i] = length of the longest increasing subsequence ending at index i

Here, i is the state.
dp[i] tells us the LIS ending exactly at nums[i]

To compute dp[i], we look at all previous indices j (0 ≤ j < i)

and check:

if (nums[j] < nums[i]) {
    dp[i] = max(dp[i], dp[j] + 1);
}

Initialization:
- Every element on its own in an LIS of length 1:

dp[i] = 1 for all i

Final Answer:

return max(dp[0], dp[1], ..., dp[n-1]);

Dry Run:

Code:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // Step 1: dp[i] will store the length of the LIS ending at index i
        vector<int> dp(n, 1); // Every element is an LIS of length 1 by itself

        // Step 2: Build the dp array
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // If nums[i] can be placed after nums[j] in an increasing sequence
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        // Step 3: Find the maximum value in dp array
        int lisLength = *max_element(dp.begin(), dp.end());
        return lisLength;
    }
};

Complexity Analysis:

Time Complexity:O(n^2)
Space Complexity:O(n)

Problem Statement

LeetCode:

Constraints:

Examples

Different Approaches

1️⃣ Brute Force Approach (Recursive) (TLE)

Intuition:

Approach:

Base cases:

Code:

Complexity Analysis:

2️⃣ Memoization

Steps to convert the recursive solution to the Memoization solution:

Note

Code:

Complexity Analysis:

3️⃣ Binary Search (Lazy Sorting)

Intuition:

Understanding:

Role of Binary Search:

Approach:

Code:

Complexity Analysis:

4️⃣ Tabulation (Bottom Up) Approach

Intuition:

Dry Run:

Code:

Complexity Analysis:

About me

Popular Posts

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory

Quick links

Tags

Newsletter

🛠️ Settings

Problem Statement

LeetCode:

Constraints:

Examples

Different Approaches

1️⃣ Brute Force Approach (Recursive) (TLE)

Intuition:

Approach:

Base cases:

Code:

Complexity Analysis:

2️⃣ Memoization

Steps to convert the recursive solution to the Memoization solution:

Note

Code:

Complexity Analysis:

3️⃣ Binary Search (Lazy Sorting)

Intuition:

Understanding:

Role of Binary Search:

Approach:

Code:

Complexity Analysis:

4️⃣ Tabulation (Bottom Up) Approach

Intuition:

Dry Run:

Code:

Complexity Analysis:

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory