Number of Longest Increasing Subsequence - Solution & Explanation
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.
Constraints:
1 <= nums.length <= 2000-106 <= nums[i] <= 106- The answer is guaranteed to fit inside a 32-bit integer.
Approach Overview
Problem Overview: You receive an integer array and must compute how many longest increasing subsequences (LIS) exist. The subsequence must be strictly increasing, and you return the count of subsequences that reach the maximum possible length.
The challenge is not just finding the LIS length. You must also track how many subsequences achieve that maximum length. This introduces a counting dimension on top of the classic LIS problem.
Approach 1: Brute Force Enumeration (Exponential Time, O(2^n) time, O(n) space)
The most direct approach generates every possible subsequence and checks whether it is strictly increasing. Track the longest length seen and count how many subsequences reach that length. This uses recursion or bitmask generation over the array. The method works for very small inputs but quickly becomes infeasible because the number of subsequences doubles with each element. It mainly helps build intuition about what qualifies as a valid increasing subsequence.
Approach 2: Dynamic Programming with Two Arrays (O(n^2) time, O(n) space)
The standard interview solution uses dynamic programming. Maintain two arrays:
length[i] stores the length of the longest increasing subsequence ending at index i. count[i] stores how many subsequences achieve that length ending at i.
Iterate through the array. For each index i, scan all previous indices j < i. If nums[j] < nums[i], the element can extend an increasing subsequence. Two cases occur: if length[j] + 1 is greater than the current best at i, update length[i] and copy count[j]. If it equals the current best, add count[j] because another LIS path reaches the same length. After processing all indices, find the global maximum length and sum counts of indices that achieve it. This approach is easy to implement and works well for typical constraints.
Approach 3: Fenwick Tree / Segment Tree Optimization (O(n log n) time, O(n) space)
The LIS counting process can also be accelerated using coordinate compression and a Binary Indexed Tree or Segment Tree. Each tree node stores the best LIS length and the number of ways to achieve it for values up to a certain rank. For every number, query the structure to find the best LIS ending with a smaller value, then update the structure with the new length and count. This reduces the nested loop and improves time complexity to O(n log n), which becomes useful for very large inputs.
Recommended for interviews: The dynamic programming solution with two arrays is the expected answer. It clearly demonstrates understanding of LIS transitions and how to track counts along with lengths. Brute force shows conceptual understanding, while the tree-based optimization demonstrates deeper knowledge of advanced data structures and performance improvements.
Approach 1: Dynamic Programming with Two Arrays
This approach utilizes two arrays to track the length of the longest increasing subsequence ending at each index and the count of such subsequences. The first array, lengths, will store the length of L.I.S. ending at each position, and the second array, counts, will store how many times such a subsequence appears. We iterate through each possible pair of indices to update these arrays accordingly.
This C function initializes two arrays, lengths and counts, with size corresponding to the input nums. It uses nested loops to compare elements, updating these arrays based on the conditions discussed. The overall length and count logic is surrounded by careful checks to decide whether to extend, begin, or merge subsequences.
Complexity
Time Complexity: O(n^2) where n is the number of elements in the input array.
Space Complexity: O(n) used for the lengths and counts arrays.
Approach 2: Dynamic Programming
We define f[i] as the length of the longest increasing subsequence ending with nums[i], and cnt[i] as the number of longest increasing subsequences ending with nums[i]. Initially, f[i]=1, cnt[i]=1. Also, we define mx as the length of the longest increasing subsequence, and ans as the number of longest increasing subsequences.
For each nums[i], we enumerate all elements nums[j] in nums[0:i-1]. If nums[j] < nums[i], then nums[i] can be appended after nums[j] to form a longer increasing subsequence. If f[i] < f[j] + 1, it means the length of the longest increasing subsequence ending with nums[i] has increased, so we need to update f[i]=f[j]+1 and cnt[i]=cnt[j]. If f[i]=f[j]+1, it means we have found a longest increasing subsequence with the same length as before, so we need to increase cnt[i] by cnt[j]. Then, if mx < f[i], it means the length of the longest increasing subsequence has increased, so we need to update mx=f[i] and ans=cnt[i]. If mx=f[i], it means we have found a longest increasing subsequence with the same length as before, so we need to increase ans by cnt[i].
Finally, we return ans.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array nums.
Approach 3: Binary Indexed Tree
We can use a binary indexed tree to maintain the length and count of the longest increasing subsequence in the prefix interval. We remove duplicates from the array nums and sort it to get the array arr. Then we enumerate each element x in nums, find the position i of x in the array arr by binary search, then query the length and count of the longest increasing subsequence in [1,i-1], denoted as v and cnt, then update the length and count of the longest increasing subsequence in [i] to v+1 and max(cnt,1). Finally, we query the length and count of the longest increasing subsequence in [1,m], where m is the length of the array arr, which is the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Arrays | Time Complexity: O(n^2) where n is the number of elements in the input array. |
| Dynamic Programming | — |
| Binary Indexed Tree | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^n) | O(n) | Conceptual understanding or very small arrays |
| Dynamic Programming with Length & Count Arrays | O(n^2) | O(n) | Standard interview solution and typical constraints |
| Fenwick Tree / Segment Tree Optimization | O(n log n) | O(n) | Large inputs where quadratic DP becomes too slow |
Video Solution
DP 47. Number of Longest Increasing Subsequences • take U forward • 197,132 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Longest Increasing Subsequence easy or hard?
Number of Longest Increasing Subsequence Python/Java solution
How to solve Number of Longest Increasing Subsequence in O(n log n)?
What is the best approach for Number of Longest Increasing Subsequence?
Is Number of Longest Increasing Subsequence asked at Google/Amazon/Meta?
What data structure is used in Number of Longest Increasing Subsequence?
What is the time complexity of Number of Longest Increasing Subsequence?
Ready to solve this problem?
Practice Number of Longest Increasing Subsequence with our built-in code editor and test cases.
Practice on FleetCode