12. Longest Increasing Subsequence

The problem can be found at the following link:

My Approach

Usually, the Longest Increasing Subsequence is a common problem solved using the O(n^2) dynamic programming approach. However, the twist in this question is the required time complexity of O(nlogn), which adds a level of complexity.

Let's now explore how I approached and solved this challenge.

I start by creating an empty vector called dp which will hold the elements identified in the longest increasing subsequence up to that point.
Next, I iterate through the input array a.
- If the current element a[i] is larger than the last element in dp, I add a[i] to the end of the dp vector.
- However, if a[i] is not larger, I employ the lower_bound function to locate the appropriate position for a[i] within the dp vector, and then replace the element at that position with a[i].
The length of the longest increasing subsequence is simply the size of the dp vector.

I understand that this method is an unconventional approach to solving dynamic programming problems. However, for a much better explanation, I recommend to Striver's explanation of this solution, which can be accessed by clicking .

Time and Auxiliary Space Complexity

Time Complexity: O(n*log(n)) due to the binary search operation in lower_bound.
Auxiliary Space Complexity: O(n) for the dp vector.

Code (C++)

class Solution
{
public:
    int longestSubsequence(int n, int a[])
    {
        vector<int> dp;
        
        dp.push_back(a[0]);
        for (int i = 1; i < n; ++i)
        {
            if (a[i] > dp.back())
                dp.push_back(a[i]);
            else
            {
                auto it = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
                dp[it] = a[i];
            }
        }

        return dp.size();
    }
};

Contribution and Support

Previous08-2023(aug)Next08-2023(aug)

Last updated 1 year ago

Was this helpful?

My Approach

Let's now explore how I approached and solved this challenge.

I start by creating an empty vector called dp which will hold the elements identified in the longest increasing subsequence up to that point.

Next, I iterate through the input array a.

If the current element a[i] is larger than the last element in dp, I add a[i] to the end of the dp vector.
However, if a[i] is not larger, I employ the lower_bound function to locate the appropriate position for a[i] within the dp vector, and then replace the element at that position with a[i].

The length of the longest increasing subsequence is simply the size of the dp vector.

Code (C++)

class Solution
{
public:
    int longestSubsequence(int n, int a[])
    {
        vector<int> dp;
        
        dp.push_back(a[0]);
        for (int i = 1; i < n; ++i)
        {
            if (a[i] > dp.back())
                dp.push_back(a[i]);
            else
            {
                auto it = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
                dp[it] = a[i];
            }
        }

        return dp.size();
    }
};