Solution Explanation for 673. Number of Longest Increasing Subsequence

This problem asks to find the number of longest increasing subsequences in a given integer array. We can solve this using dynamic programming or a more optimized approach using a Binary Indexed Tree (BIT).

Solution 1: Dynamic Programming

This approach uses two DP arrays:

• f[i]: Stores the length of the longest increasing subsequence ending at index i.
• cnt[i]: Stores the count of longest increasing subsequences ending at index i.

The algorithm iterates through the array. For each element nums[i], it compares it with previous elements nums[j] (where j < i). If nums[j] < nums[i], it means we can potentially extend an increasing subsequence.

• If f[i] < f[j] + 1: This means we've found a longer increasing subsequence ending at i. Update f[i] and set cnt[i] to cnt[j] (because we're inheriting the count from the subsequence ending at j).
• If f[i] == f[j] + 1: This means we've found another increasing subsequence of the same length. Add cnt[j] to cnt[i].

After iterating through all elements, we find the maximum length (mx) among all f[i] values. Then, we iterate again to find the sum of cnt[i] values where f[i] == mx. This sum represents the total number of longest increasing subsequences.

Time Complexity: O(n^2) due to the nested loops. Space Complexity: O(n) to store the f and cnt arrays.

Solution 2: Binary Indexed Tree (BIT)

This approach is more efficient than the pure DP solution. It leverages a Binary Indexed Tree to efficiently update and query the maximum length and count of increasing subsequences.

1. Preprocessing: Remove duplicates from the input array nums and sort the unique elements into a new array arr. This array represents the possible values that can be part of an increasing subsequence.

2. Iteration and Updates: Iterate through the original nums array. For each element x:

   • Perform a binary search on arr to find the index i where arr[i-1] < x <= arr[i]. This i represents the position of x in the sorted unique elements.
   • Use the BIT to query the maximum length (v) and count (cnt) of increasing subsequences up to index i-1.
   • Update the BIT at index i with the new length (v+1) and count (max(cnt,1)). The max(cnt, 1) ensures that even if a new longest subsequence starts at a certain value, it's still counted.

3. Final Query: Finally, query the BIT at the end (index m, where m is the length of arr). This query will return the total count of the longest increasing subsequences.

Time Complexity: O(n log n), dominated by the binary search and BIT operations. Space Complexity: O(n) to store the arr array and the BIT.

Code Examples (Python for both solutions):

Solution 1 (Dynamic Programming):

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        f = [1] * n
        cnt = [1] * n
        mx = 1
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if f[i] < f[j] + 1:
                        f[i] = f[j] + 1
                        cnt[i] = cnt[j]
                    elif f[i] == f[j] + 1:
                        cnt[i] += cnt[j]
            mx = max(mx, f[i])
 
        ans = 0
        for i in range(n):
            if f[i] == mx:
                ans += cnt[i]
        return ans
 

Solution 2 (Binary Indexed Tree):

import bisect
 
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
 
    def update(self, i, val):
        i += 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i
 
    def query(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res
 
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        unique_nums = sorted(list(set(nums)))
        n = len(unique_nums)
        bit_len = BIT(n)
        bit_cnt = BIT(n)
        max_len = 0
        for num in nums:
            idx = bisect.bisect_left(unique_nums, num)
            len_so_far = bit_len.query(idx -1) +1
            count_so_far = bit_cnt.query(idx-1) if idx > 0 else 1
            bit_len.update(idx, len_so_far - bit_len.query(idx))
            bit_cnt.update(idx, count_so_far)
            max_len = max(max_len, len_so_far)
            
        return bit_cnt.query(n-1)

Remember to handle edge cases like empty input arrays appropriately. The BIT solution is generally preferred for larger datasets due to its better time complexity.