algoadvance

Leetcode 300. Longest Increasing Subsequence

Problem Statement

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

Example:

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.

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Clarifying Questions

1. Can the input array contain duplicates?
   • Yes, but the subsequence has to strictly increase, meaning duplicates cannot be part of the same subsequence.
2. Is the longest increasing subsequence (LIS) required, or just its length?
   • Only the length of the longest increasing subsequence is required.

Strategy

To solve this problem, we can use Dynamic Programming (DP). Here’s a detailed plan:

1. DP Array Initialization:
   • Let dp[i] represent the length of the longest increasing subsequence that ends with the element at index i.
2. State Transition:
   • For each element nums[i], check all previous elements nums[j] where (j < i) and nums[j] < nums[i]. Update dp[i] to be the maximum of dp[i] and dp[j] + 1.
3. Base Case:
   • Every element itself can be a subsequence, so initialize dp[i] = 1 for all i.
4. Result:
   • The length of the longest increasing subsequence will be the maximum value in the dp array.

Time Complexity

• Time Complexity: O(N^2), where N is the length of the input array nums. This is because, for each element, we potentially compare it with all previous elements.
• Space Complexity: O(N), where N is the length of the input array nums. This is due to the extra space required for the dp array.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> dp(nums.size(), 1);
        int maxLength = 1;
        
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = std::max(dp[i], dp[j] + 1);
                }
            }
            maxLength = std::max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
};

Explanation:

• Initialization: dp array is initiated with all entries as 1, since each element is a subsequence of length 1 by itself.
• Nested Loops: The outer loop iterates over each element i, and the inner loop compares element i with all previous elements j.
• Condition Check: If nums[i] > nums[j], update dp[i] as the maximum of dp[i] and dp[j] + 1.
• Max Length Update: After processing each i, update maxLength with the maximum value found in dp[i].

Thus, the algorithm efficiently computes the length of the longest increasing subsequence in O(N^2) time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?