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] <= 106The goal of #673 Number of Longest Increasing Subsequence is not only to find the length of the longest increasing subsequence (LIS) but also to count how many such subsequences exist. A common approach uses Dynamic Programming where two arrays track the length of the LIS ending at each index and the count of subsequences achieving that length. By iterating through previous elements, you update these arrays whenever a valid increasing extension is found.
This DP approach runs in O(n²) time and is often sufficient for moderate input sizes. For optimization, advanced solutions use data structures like a Binary Indexed Tree (Fenwick Tree) or Segment Tree combined with coordinate compression. These structures efficiently store pairs of (length, count) and query the best subsequence ending with smaller values. This reduces the time complexity to O(n log n) while maintaining correct counting logic.
The key idea is to track both the maximum subsequence length and the number of ways to achieve it.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming | O(n²) | O(n) |
| Binary Indexed Tree / Segment Tree with Compression | O(n log n) | O(n) |
NeetCode
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.
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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5int findNumberOfLIS(int* nums, int numsSize)
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Tracking only the LIS length is not enough because multiple subsequences may achieve that same maximum length. Maintaining both the length and the count allows the algorithm to correctly accumulate the number of distinct longest subsequences.
Yes, variations of LIS counting problems appear in technical interviews at large tech companies. Interviewers use it to test understanding of dynamic programming, state transitions, and optimization using advanced data structures.
The typical solution uses dynamic programming with two arrays to track the LIS length and the count of sequences ending at each index. For better performance, Binary Indexed Trees or Segment Trees with coordinate compression can reduce the time complexity to O(n log n).
Dynamic programming arrays are the most common structure for this problem. For optimized solutions, a Fenwick Tree (Binary Indexed Tree) or Segment Tree can efficiently maintain the best subsequence length and the number of ways for smaller values.