https://leetcode.com/problems/number-of-longest-increasing-subsequence

The idea of my solution is to use so-called Patience sort: https://en.wikipedia.org/wiki/Patience_sorting

The idea is to keep several decks, where numbers in each deck are decreasing. Also when we see new card, we need to put it to the end of the leftest possible deck. Also we have paths: corresponing number of LIS, ending with given num. That is in paths[0] we keep number of LIS with length 1, in paths[k] we keep number of LIS with length k+1. (we keep cumulative sums) Also we keep ends_decks list to have quick access to end of our decks.

Property: It can be proved, that each LIS can be formed as choosing not more than one number from each deck and choosing them, looking at decks from left to right.

Imagine, that we have nums = [1,3,5,4,7,10,8,2,8], then we have the following decks and paths step by step:

decks = [[-1]] paths = [[0, 1]] decks = [[-1], [-3]] paths = [[0, 1], [0, 1]] decks = [[-1], [-3], [-5]] paths = [[0, 1], [0, 1], [0, 1]] decks = [[-1], [-3], [-5, -4]] paths = [[0, 1], [0, 1], [0, 1, 2]] decks = [[-1], [-3], [-5, -4], [-7]] paths = [[0, 1], [0, 1], [0, 1, 2], [0, 2]] decks = [[-1], [-3], [-5, -4], [-7], [-10]] paths = [[0, 1], [0, 1], [0, 1, 2], [0, 2], [0, 2]] decks = [[-1], [-3], [-5, -4], [-7], [-10, -8]] paths = [[0, 1], [0, 1], [0, 1, 2], [0, 2], [0, 2, 4]] decks = [[-1], [-3, -2], [-5, -4], [-7], [-10, -8]] paths = [[0, 1], [0, 1, 2], [0, 1, 2], [0, 2], [0, 2, 4]] decks = [[-1], [-3, -2], [-5, -4], [-7], [-10, -8, -8]] paths = [[0, 1], [0, 1, 2], [0, 1, 2], [0, 2], [0, 2, 4, 6]]

We use negative numbers, so each deck is sorted in increasing way instead of decreasing.

When we see new num, then we first find deck_idx: number of deck we need to put this num. Now, we want to find number of LIS, ending with this num: for this we need to look at previous deck and find the place of num inside this deck: here we use our property, we update our n_path.

Now, we need to decide where we put this number:

  1. If our deck_idx is equal to len(decks), it means, that we need to create new deck: we create new deck with one element, update ends_decks and also append n_paths to our paths.
  2. In opposite case, we need to add nums to the end of corresponding deck, again update ends_decks and update our pathcs[deck_idx]: it will consist of two parts: n_paths: number of paths, such that previous element is from previous or before decks. Also we have paths[deck_idx][-1], because we keep cumulative sums inside.

Finally, we return paths[-1][-1], it is number of LIS with the biggest length.

Complexity is O(n log n), because for each new num we process it in O(log n). Space complexity is O(n). When I run it, i have times, I have times from 60ms to 72ms, where 60ms beats 100% of python solutions.

class Solution:
    def findNumberOfLIS(self, nums):
        if not nums: return 0
    
        decks, ends_decks, paths = [], [], []
        for num in nums:
            deck_idx = bisect.bisect_left(ends_decks, num)
            n_paths = 1
            if deck_idx > 0:
                l = bisect.bisect(decks[deck_idx-1], -num)
                n_paths = paths[deck_idx-1][-1] - paths[deck_idx-1][l]
                
            if deck_idx == len(decks):
                decks.append([-num])
                ends_decks.append(num)
                paths.append([0,n_paths])
            else:
                decks[deck_idx].append(-num)
                ends_decks[deck_idx] = num
                paths[deck_idx].append(n_paths + paths[deck_idx][-1])
              
        return paths[-1][-1]

Shorter version it can be written in shorter version, if we prefill our decks, decks_ends and paths first. However I do no know if we can do binary search in python by key: if we can, we can remove ends_decks at all and simplify it even more. Can somebody help me with it?

class Solution:
    def findNumberOfLIS(self, nums):
        if not nums: return 0
        n = len(nums) + 1
    
        decks, ends_decks, paths = [[] for _ in range(n)], [float("inf")]*n, [[0] for _ in range(n)]
        for num in nums:
            idx = bisect.bisect_left(ends_decks, num)
            n_paths = 1
            if idx > 0:
                l = bisect.bisect(decks[idx-1], -num)
                n_paths = paths[idx-1][-1] - paths[idx-1][l]
            
            decks[idx].append(-num)
            ends_decks[idx] = num
            paths[idx].append(n_paths + paths[idx][-1])
                
        return paths[paths.index([0]) - 1][-1]

PS: see also my solution of problem 300: Longest Increasing Subsequence:

If you like the solution, you can upvote it on leetcode discussion section: Problem 0673