algoadvance

Leetcode 300. Longest Increasing Subsequence

Problem Statement

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

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:

Clarifying Questions

  1. Q: Can the input array contain negative numbers or zero? A: Yes, as per the constraints, the range of numbers is -10^4 to 10^4.

  2. Q: Is the sequence strictly increasing required? A: Yes, each subsequent element in the subsequence must be strictly greater than the previous one.

  3. Q: Can we have an empty array as input? A: No, as per the constraints, the minimum length of nums is 1.

Strategy

We’ll use Dynamic Programming (DP) to solve this problem. Here’s a step-by-step approach:

  1. DP Array Initialization:
    • Initialize a DP array dp where dp[i] represents the length of the longest increasing subsequence that ends at index i.
    • Initially, each element in dp should be 1, as the minimum length of an increasing subsequence ending at any element is 1 (the element itself).
  2. DP Array Update:
    • For each element nums[i], check all previous elements nums[j] where 0 <= j < i.
    • If nums[j] < nums[i], then we can extend the subsequence ending at j to include nums[i]. Hence, update dp[i] = max(dp[i], dp[j] + 1).
  3. Result Computation:
    • The length of the longest increasing subsequence will be the maximum value in the dp array.

Time Complexity

Code

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int[] dp = new int[n];
        int maxLength = 1;
        
        // Initialize dp array
        Arrays.fill(dp, 1);
        
        // Fill dp array
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
}

Explanation

  1. Initialization:
    • We initialize a dp array where each element is set to 1 because the smallest increasing subsequence at any point is the element itself.
  2. DP Update:
    • For each nums[i], check all indices j before i. If nums[j] < nums[i], update dp[i] by comparing its current value with dp[j] + 1.
  3. Update maxLength:
    • Throughout each iteration, update maxLength to record the maximum value in the dp array.
  4. Return Result:
    • Finally, return maxLength, which contains the length of the longest increasing subsequence.

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