Last updated on January 12th, 2025 at 10:24 pm
Here, we see a Number of Longest Increasing Subsequence LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Level of Question
Medium
Number of Longest Increasing Subsequence LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is Dynamic Programming (DP). Specifically, it is a DP with State Tracking pattern. The problem involves finding the number of Longest Increasing Subsequences (LIS) in an array, which requires maintaining two arrays:
lis(orlengths/tracker/dp): Tracks the length of the LIS ending at each index.count(orfrequency/counts): Tracks the number of LIS ending at each index.
3. Code Implementation in Different Languages
3.1 Number of Longest Increasing Subsequence C++
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
const int n = nums.size();
vector<int> lis(n,1);
vector<int> count(n,1);
int maxLen = 1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
if(lis[j] + 1 > lis[i]){
lis[i] = lis[j] + 1;
count[i] = count[j];
}
else if(lis[j]+1 == lis[i]){
count[i] += count[j];
}
}
}
maxLen = max(maxLen,lis[i]);
}
int numOfLIS = 0;
for(int i=0;i<n;i++){
if(lis[i]==maxLen)
numOfLIS += count[i];
}
return numOfLIS;
}
};
3.2 Number of Longest Increasing Subsequence Java
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
int[] count = new int[n];
Arrays.fill(dp, 1);
Arrays.fill(count, 1);
int maxLength = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
count[i] = count[j];
} else if (dp[j] + 1 == dp[i]) {
count[i] += count[j];
}
}
}
maxLength = Math.max(maxLength, dp[i]);
}
int result = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == maxLength) {
result += count[i];
}
}
return result;
}
}
3.3 Number of Longest Increasing Subsequence JavaScript
var findNumberOfLIS = function(nums) {
let tracker = new Array(nums.length).fill(1);
let frequency = new Array(nums.length).fill(1);
for(let i = 0; i < nums.length; i++){
for(let j = 0; j < i; j++){
if(nums[j] < nums[i]){
if(tracker[i] < tracker[j]+1){
tracker[i] = tracker[j] + 1;
frequency[i] = frequency[j];
} else if(tracker[i] === tracker[j] + 1){
frequency[i] += frequency[j];
}
}
}
}
const longestPath = Math.max(...tracker);
let result = 0;
for(let k = 0; k < nums.length; k++){
if(tracker[k] === longestPath) result += frequency[k];
}
return result;
};
3.4 Number of Longest Increasing Subsequence Python
class Solution(object):
def findNumberOfLIS(self, nums):
n = len(nums)
if n <= 1:
return n
lengths = [1] * n
counts = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
if lengths[j] + 1 > lengths[i]:
lengths[i] = lengths[j] + 1
counts[i] = counts[j]
elif lengths[j] + 1 == lengths[i]:
counts[i] += counts[j]
max_length = max(lengths)
return sum(count for length, count in zip(lengths, counts) if length == max_length)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n²) | O(n) |
| Java | O(n²) | O(n) |
| JavaScript | O(n²) | O(n) |
| Python | O(n²) | O(n) |
- This code uses Dynamic Programming with State Tracking to solve the problem of finding the number of Longest Increasing Subsequences in an array.
- It efficiently tracks the LIS length and count for each index using two arrays, and the final result is computed by summing up the counts of LIS of maximum length.
- The time complexity is O(n²) due to the nested loops, and the space complexity is O(n) due to the auxiliary arrays.