I have been practicing C++ programming for interviews recently. I came into this problem again. This is a very interesting problem:
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].
First of all, we know it is easy to get the length of the longest increasing subsequence (LIS). This can be done by O(n*log(n)) time. However, this problem is asking the number of LIS that have the longest length.
The naïve solution to such a problem falls easily into the category of dynamic programming (DP) where you can make decision at each index - whether to include it in the final LIS or not. This is what the majority of people are doing. Unfortunately, this is O(n^2) time complexity and there exists better solutions.
The interviewer might just expect the optimal solution from you. I am providing the O(n log(n)) solution here, with binary searches on indexes. There are a lot of tricks played here, but in the end we can see my solution is O(n*log(n)).
The idea is simple; we keep track of the longest increasing sequence (LIS) as well as the number of LIS sequences ending with the current element.
For example, [1, 3, 5, 4, 7] as the input.
I assume it is easy to see LIS for the first 3 elements is [1, 3, 5].
When we see 4, we can update LIS to have [1,3,4], but we should not discard the sequence [1, 3, 5] since it may contribute to later LIS sequences. This LIS has a length 3 (maximum index is 2), so we keep a vector:
table[2] = {[5,1], [4,1]}
indicating at LIS index 2 we could have 1 sequence ending with 5, and another sequence ending with 4.
Then we see 7. We see 7 has to be added to the end of the LIS, but it could be added to the LIS ending with 5 or 4. So we will have table[3] = {[7, 2]}.
In general, for any current element, we will need to find out the index just before its insertion point in LIS. In the previous example, for number 7 to be inserted at index 3, we need to check table[2] to update the number of possible paths for the current number. In my program, this is what k is (line 13, 18).
Also, for each LIS insertion at index i, we are inserting it in descending order, so it would be easy to find out the exact place in table[i] using binary search. In my program, I used negative number for easy binary search (line 15, 21).
Another trick is I am only keeping the prefix sum of all paths for table[i] (line 29). In this way, the number of paths k can be obtained in O(1) (line 18).
After submitting the solution, we can see:
Runtime: 16 ms, faster than 98.51% of C++ online submissions for Number of Longest Increasing Subsequence.
Memory Usage: 15.5 MB, less than 6.11% of C++ online submissions for Number of Longest Increasing Subsequence.