Number of Longest Increasing Subsequence — Solution
Number of Longest Increasing Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Longest Increasing Subsequence is a medium coding problem on arrays, dynamic programming and binary indexed tree, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Binary Indexed Tree
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, return the number of longest strictly increasing subsequences.
Example 1
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest are [1,3,4,7] and [1,3,5,7].
Example 2
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The longest has length 1, and there are five of them.
Example 3
Input: nums = [1]
Output: 1
Constraints
1 <= nums.length <= 30-1000 <= nums[i] <= 1000
Hints for Number of Longest Increasing Subsequence
Hint 1
Extend the usual O(n²) LIS with a second table: how many longest chains end at each index.
Hint 2
When a longer chain is found, the count is replaced; when an equally long one is found, the counts add.
Hint 3
The answer sums the counts at every index whose chain length equals the global maximum.
How to solve Number of Longest Increasing Subsequence
Run the O(n²) LIS with a second table counting how many longest chains end at each index; a strictly longer chain replaces the count, an equal one adds to it.
Approach
- For each
iand eachj < iwithnums[j] < nums[i]: iflength[j] + 1 > length[i], setlength[i]andcount[i] = count[j]; if equal,count[i] += count[j]. - Sum
count[i]over indices whoselength[i]equals the global maximum.
Why it works
Every longest chain ending at i passes through some j with length[j] = length[i] - 1, and distinct j (or distinct chains through the same j) give distinct chains, so the counts add exactly.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Use
count[i] = count[j]on a strict improvement, not+=.
Reference solution
Python
def findNumberOfLIS(nums) -> int:
n = len(nums)
length = [1] * n
count = [1] * n
best = 1
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
if length[j] + 1 > length[i]:
length[i] = length[j] + 1
count[i] = count[j]
elif length[j] + 1 == length[i]:
count[i] += count[j]
best = max(best, length[i])
return sum(count[i] for i in range(n) if length[i] == best)Java
public static int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] len = new int[n];
int[] count = new int[n];
Arrays.fill(len, 1);
Arrays.fill(count, 1);
int best = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
count[i] = count[j];
} else if (len[j] + 1 == len[i]) {
count[i] += count[j];
}
}
}
if (len[i] > best) best = len[i];
}
int total = 0;
for (int i = 0; i < n; i++) {
if (len[i] == best) total += count[i];
}
return total;
}C++
int findNumberOfLIS(vector<int>& nums) {
int n = (int) nums.size();
vector<int> len(n, 1), count(n, 1);
int best = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
count[i] = count[j];
} else if (len[j] + 1 == len[i]) {
count[i] += count[j];
}
}
}
best = max(best, len[i]);
}
int total = 0;
for (int i = 0; i < n; i++) {
if (len[i] == best) total += count[i];
}
return total;
}JavaScript
var findNumberOfLIS = function(nums) {
const n = nums.length;
const len = new Array(n).fill(1);
const count = new Array(n).fill(1);
let best = 1;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
count[i] = count[j];
} else if (len[j] + 1 === len[i]) {
count[i] += count[j];
}
}
}
if (len[i] > best) best = len[i];
}
let total = 0;
for (let i = 0; i < n; i++) {
if (len[i] === best) total += count[i];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming