Watch 10 video solutions for Number of Longest Increasing Subsequence, a medium level problem involving Array, Dynamic Programming, Binary Indexed Tree. This walkthrough by NeetCode has 46,224 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106Problem 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 | 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 |