algoadvance

Leetcode 673. Number of Longest Increasing Subsequence

Problem Statement

Given an unsorted array of integers nums, return the number of longest increasing subsequences.

Example:

• Example 1:
  • Input: nums = [1,3,5,4,7]
  • Output: 2
  • Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
• Example 2:
  • Input: nums = [2,2,2,2,2]
  • Output: 5
  • Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so the answer is 5.

Clarifying Questions

1. What should be returned if the input array is empty?
   • If nums is empty, the number of longest increasing subsequences is 0.
2. What is the range of values for the input array?
   • The problem does not specify any range constraints; we assume typical integer values are used.
3. Can elements in the array be negative?
   • Yes, elements can be any integers, including negative values.

Strategy

To solve this problem, we’ll use dynamic programming with the following steps:

1. Initial Setup:
   • Create two arrays: lengths and counts. lengths[i] will hold the length of the longest increasing subsequence that ends with nums[i]. counts[i] will hold the number of such subsequences ending at nums[i].
2. Populate the Arrays:
   • Iterate through each element from left to right. For each element nums[i], iterate through all previous elements nums[j] (where j < i).
   • If nums[i] > nums[j], it means nums[i] can extend the subsequence ending at nums[j].
   • Depending on the length of subsequences, update lengths[i] and counts[i].
3. Derive the Result:
   • Identify the maximum length from the lengths array.
   • Sum up all the counts corresponding to this maximum length.

Code

public class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int n = nums.length;
        int[] lengths = new int[n];
        int[] counts = new int[n];

        Arrays.fill(lengths, 1);
        Arrays.fill(counts, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (lengths[j] + 1 > lengths[i]) {
                        lengths[i] = lengths[j] + 1;
                        counts[i] = counts[j];
                    } else if (lengths[j] + 1 == lengths[i]) {
                        counts[i] += counts[j];
                    }
                }
            }
        }

        int maxLength = 0;
        for (int length : lengths) {
            maxLength = Math.max(maxLength, length);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            if (lengths[i] == maxLength) {
                result += counts[i];
            }
        }

        return result;
    }
}

Time Complexity

• Time Complexity: O(n^2), where n is the number of elements in the array. This is due to the nested loops iterating through the array.
• Space Complexity: O(n), for the lengths and counts arrays.

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?