algoadvance

Leetcode 673. Number of Longest Increasing Subsequence

Problem Statement

You are given an integer array nums of size n. Return the number of longest increasing subsequences.

Example:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 5, 7] and [1, 3, 4, 7].

Clarifying Questions

  1. What is the range of the input size n?
    • The input size can range from 1 to 2000.
  2. Can the elements in nums be negative?
    • The problem statement does not specify restrictions on nums values, so we assume they can be any integers.
  3. What should we return if nums is empty?
    • Given the constraints (1 ≤ n ≤ 2000), nums will not be empty.

Strategy

  1. Dynamic Programming Arrays:
    • length[i] will store the length of the longest increasing subsequence that ends in nums[i].
    • count[i] will store the number of longest increasing subsequences that end in nums[i].
  2. Initialization:
    • Initialize both length and count arrays with 1s, since every element can be a subsequence of length 1 by itself.
  3. Iterate and Update:
    • Use nested loops to update the length and count arrays.
    • For each pair of indices (i, j) such that i > j and nums[i] > nums[j]:
      • If length[j] + 1 > length[i], update length[i] and set count[i] = count[j].
      • If length[j] + 1 == length[i], increment count[i] by count[j].
  4. Result Calculation:
    • The maximum value in length array indicates the length of the longest increasing subsequence.
    • Sum up the values in the count array for indices where the length matches the maximum length.

Time Complexity

Code

#include <vector>
#include <algorithm>

int findNumberOfLIS(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    
    std::vector<int> length(n, 1); // length[i] -> length of LIS ending at index i
    std::vector<int> count(n, 1); // count[i] -> number of LIS ending at index i
    
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                    count[i] = count[j];
                } else if (length[j] + 1 == length[i]) {
                    count[i] += count[j];
                }
            }
        }
    }
    
    int longest = *std::max_element(length.begin(), length.end());
    int result = 0;
    
    for (int i = 0; i < n; ++i) {
        if (length[i] == longest) {
            result += count[i];
        }
    }
    
    return result;
}

This code correctly finds the number of longest increasing subsequences in a given array nums using a dynamic programming approach. Make sure to test it with various edge cases to ensure its correctness and efficiency.

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