Number of Longest Increasing Subsequence LeetCode Solution
Problem Description
The Number of Longest Increasing Subsequence LeetCode Solution problem involves finding the number of longest increasing subsequences in an array. Given an unsorted array of integers, the task is to find the length of the longest increasing subsequence and the number of such subsequences with that maximum length.
Intuition
The problem can be approached using dynamic programming. We can maintain two arrays: length to store the length of the longest increasing subsequence ending at each index, and count to store the number of such subsequences. We iterate through the array, updating these arrays based on the increasing subsequence conditions.
Solution Approach
- Initialize two arrays:
lengthof sizen(length of the input array) andcountof sizen, both initialized to 1. - Iterate through the array with two nested loops. For each pair of indices (i, j) where
nums[i] < nums[j], updatelength[j]andcount[j]based on the conditions. - Find the maximum length in the
lengtharray. - Iterate through the
lengtharray and accumulate the counts of subsequences with maximum length. - Return the maximum length and the count of such subsequences.
Example Walkthrough
Consider the following array: [1, 3, 5, 4, 7]
- Initialize
lengthandcountarrays:[1, 1, 1, 1, 1]and[1, 1, 1, 1, 1]. - Iterate through the array:
- For
nums[1] = 3, updatelength[1]to 2 andcount[1]to 1. - For
nums[2] = 5, updatelength[2]to 3 andcount[2]to 1. - For
nums[3] = 4, updatelength[3]to 3 andcount[3]to 1. - For
nums[4] = 7, updatelength[4]to 4 andcount[4]to 2.
- For
- Find the maximum length, which is 4.
- Accumulate counts of subsequences with length 4, which is 2.
- Return the maximum length (4) and the count (2).
Code Solutions
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
lengths = [1] * n
counts = [1] * n
for j in range(n):
for i in range(j):
if nums[i] < nums[j]:
if lengths[i] + 1 > lengths[j]:
lengths[j] = lengths[i] + 1
counts[j] = counts[i]
elif lengths[i] + 1 == lengths[j]:
counts[j] += counts[i]
max_length = max(lengths)
result = sum(count for length, count in zip(lengths, counts) if length == max_length)
return result
class Solution {
public:
int findNumberOfLIS(vector& nums) {
if (nums.empty())
return 0;
int n = nums.size();
vector lengths(n, 1);
vector counts(n, 1);
for (int j = 0; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
if (lengths[i] + 1 > lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
}
int maxLength = *max_element(lengths.begin(), lengths.end());
int result = 0;
for (int k = 0; k < n; k++) {
if (lengths[k] == maxLength)
result += counts[k];
}
return result;
}
};
class Solution {
public int findNumberOfLIS(int[] nums) {
if (nums == null || 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 j = 0; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
if (lengths[i] + 1 > lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
}
int maxLength = Arrays.stream(lengths).max().orElse(0);
int result = 0;
for (int k = 0; k < n; k++) {
if (lengths[k] == maxLength)
result += counts[k];
}
return result;
}
}
Time and Space Complexity
Time Complexity: O(n^2) – Two nested loops are used to iterate through the array.
Space Complexity: O(n) – Additional arrays lengths and counts of size n are used.
