Leetcode 673: Number of Longest Increasing Subsequence
grid47 Exploring patterns and algorithms
Aug 31, 2024
7 min read
Solution to LeetCode 673: Number of Longest Increasing Subsequence Problem
Given an integer array nums, return the number of distinct longest increasing subsequences.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers `nums`.
Example: nums = [3, 2, 6, 4, 5]
Constraints:
• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6
Output: Return the number of distinct longest increasing subsequences.
Example: 3
Constraints:
• The answer is guaranteed to fit within a 32-bit integer.
Goal: Find the number of distinct longest increasing subsequences.
Steps:
• 1. Use dynamic programming to track the length of the longest increasing subsequences ending at each element.
• 2. Maintain a count of how many subsequences achieve the longest length for each element.
• 3. Sum the counts for the subsequences that have the maximum length.
Goal: The length of the `nums` array and the value of the elements are bounded as described.
Steps:
• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6
Assumptions:
• Subsequences are strictly increasing, meaning each element in a subsequence must be greater than the previous element.
• Input: nums = [1, 3, 5, 4, 7]
• Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7], both of length 4.
• Input: nums = [2, 2, 2, 2, 2]
• Explanation: Since there are no strictly increasing subsequences, the longest subsequences are of length 1, and there are 5 such subsequences.
Approach: We use dynamic programming to track the length of the longest increasing subsequences at each index and count the number of such subsequences.
Observations:
• We can iterate through the array and for each element, compare it with previous elements to build subsequences.
• The key observation is that we need to track both the length and the count of subsequences for each element.
Steps:
• 1. Create an array `len[]` to store the length of the longest increasing subsequence ending at each index.
• 2. Create an array `cnt[]` to store the number of ways to form the longest subsequence at each index.
• 3. For each element, compare it with previous elements to update `len[]` and `cnt[]`.
• 4. Return the sum of `cnt[]` for elements that correspond to the longest subsequences.
Empty Inputs:
• This problem doesn't have an empty input as `nums` is guaranteed to have at least one element.
Large Inputs:
• Ensure the solution can handle arrays up to the maximum size (2000 elements).
Special Values:
• If all elements in `nums` are equal, the longest subsequence length is 1, and the answer is the number of elements in `nums`.
Constraints:
• Handle large input sizes efficiently using dynamic programming.
This is the function definition for `findNumberOfLIS`, which calculates the number of longest increasing subsequences (LIS) in the input array `nums`.
2 : Variable Initialization
Initialize necessary variables to store the result, the size of the input array `nums`, the maximum length of increasing subsequences found, and two vectors `len` and `cnt` to store the lengths and counts of LIS for each element.
3 : Variable Initialization
int res =0, n = nums.size(), max_len =0;
Here, we initialize `res` to 0 (to store the number of LIS), `n` to the size of the input array `nums`, and `max_len` to 0 (to store the maximum length of LIS found so far).
4 : Array Initialization
vector<int> len(n, 0), cnt(n, 0);
The vectors `len` and `cnt` are initialized to size `n` with all elements set to 0. `len[i]` will store the length of the LIS ending at index `i`, and `cnt[i]` will store the count of such LIS.
5 : Outer Loop
for(int i =0; i < n; i++) {
The outer loop iterates through each element of the array `nums`.
6 : Set Initial Values for Each Element
cnt[i] =1;
For each element `i`, we initialize `cnt[i]` to 1, as the minimum count of LIS that ends at `i` is 1 (the element itself).
7 : Set Initial Values for Each Element
len[i] =1;
Similarly, we initialize `len[i]` to 1, as the minimum length of LIS ending at `i` is 1 (the element itself).
8 : Inner Loop
for(int j =0; j < i; j++) {
The inner loop checks all previous elements `j` before index `i` to see if they form an increasing subsequence with `nums[i]`.
9 : Condition: Check for Increasing Subsequence
if(nums[j] < nums[i]) {
This condition checks if `nums[j]` is less than `nums[i]`, meaning that `nums[i]` can extend an increasing subsequence ending at `j`.
10 : Update Count for Equal Lengths
if(len[j] +1== len[i]) cnt[i] += cnt[j];
If the length of the LIS ending at `j` plus one equals the length of the LIS ending at `i`, we add the count of LIS ending at `j` to the count for `i`.
11 : Update Length and Count for Longer LIS
if(len[j] +1> len[i]) {
If the length of the LIS ending at `j` plus one is greater than the current length at `i`, we update `len[i]` and set `cnt[i]` to the count of LIS at `j`.
12 : Update Length and Count for Longer LIS
len[i] = len[j] +1;
Update the length of the LIS ending at `i` to be the length of the LIS at `j` plus one.
13 : Update Length and Count for Longer LIS
cnt[i] = cnt[j];
Set the count of LIS ending at `i` to the count of LIS at `j`.
14 : Update Result for Maximum Length
if(max_len == len[i]) res += cnt[i];
If the length of the LIS at `i` is equal to the maximum length found so far, add the count of LIS at `i` to the result `res`.
15 : Update Result for New Maximum Length
if(max_len < len[i]) {
If the length of the LIS at `i` is greater than the current maximum length, update `res` and `max_len`.
16 : Update Result for New Maximum Length
res = cnt[i];
Set `res` to the count of LIS at `i` since it's the new maximum length.
17 : Update Result for New Maximum Length
max_len = len[i];
Update `max_len` to the length of the LIS at `i`.
18 : Return Result
return res;
The final step is to return the number of LIS.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The worst-case time complexity is O(n^2) due to two nested loops iterating over the array.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage of the `len[]` and `cnt[]` arrays.
