673. Number of Longest Increasing Subsequence LeetCode Solution
In this guide, you will get 673. Number of Longest Increasing Subsequence LeetCode Solution with the best time and space complexity. The solution to Number of Longest Increasing Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
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 output 5.
Constraints:
1 <= nums.length <= 2000
-106 <= nums[i] <= 106
The answer is guaranteed to fit inside a 32-bit integer.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
673. Number of Longest Increasing Subsequence LeetCode Solution in C++
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
int maxLength = 0;
// length[i] := the length of LIS's ending in nums[i]
vector<int> length(n, 1);
// count[i] := the number of LIS's ending in nums[i]
vector<int> count(n, 1);
// Calculate `length` and `count` arrays.
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
if (nums[j] < nums[i])
if (length[i] < length[j] + 1) {
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[i] == length[j] + 1) {
count[i] += count[j];
}
// Get the number of LIS.
for (int i = 0; i < n; ++i)
if (length[i] > maxLength) {
maxLength = length[i];
ans = count[i];
} else if (length[i] == maxLength) {
ans += count[i];
}
return ans;
}
}; /* code provided by PROGIEZ */
673. Number of Longest Increasing Subsequence LeetCode Solution in Java
class Solution {
public int findNumberOfLIS(int[] nums) {
final int n = nums.length;
int ans = 0;
int maxLength = 0;
// length[i] := the length of the LIS ending in nums[i]
int[] length = new int[n];
// count[i] := the number of LIS's ending in nums[i]
int[] count = new int[n];
Arrays.fill(length, 1);
Arrays.fill(count, 1);
// Calculate the `length` and `count` arrays.
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
if (nums[j] < nums[i])
if (length[i] < length[j] + 1) {
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[i] == length[j] + 1) {
count[i] += count[j];
}
// Get the number of LIS.
for (int i = 0; i < n; ++i)
if (length[i] > maxLength) {
maxLength = length[i];
ans = count[i];
} else if (length[i] == maxLength) {
ans += count[i];
}
return ans;
}
} // code provided by PROGIEZ
673. Number of Longest Increasing Subsequence LeetCode Solution in Python
class Solution:
def findNumberOfLIS(self, nums: list[int]) -> int:
ans = 0
maxLength = 0
# length[i] := the length of the LIS ending in nums[i]
length = [1] * len(nums)
# count[i] := the number of LIS's ending in nums[i]
count = [1] * len(nums)
# Calculate the `length` and `count` arrays.
for i, num in enumerate(nums):
for j in range(i):
if nums[j] < num:
if length[i] < length[j] + 1:
length[i] = length[j] + 1
count[i] = count[j]
elif length[i] == length[j] + 1:
count[i] += count[j]
# Get the number of LIS.
for i, l in enumerate(length):
if l > maxLength:
maxLength = l
ans = count[i]
elif l == maxLength:
ans += count[i]
return ans # code by PROGIEZ
