Problem Statement

Given an integer array nums, return the number of longest increasing subsequences.

A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements

Note: Sequences should be strictly increasing.

Examples

1. Example 1:

   • Input: nums = [2, 6, 4, 3, 5]
   • Expected Output: 2
   • Explanation: The longest increasing subsequences are [2, 3, 5] and [2, 4, 5], both having a length of 3. Therefore, there are two such subsequences.

2. Example 2:

   • Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
   • Expected Output: 4
   • Explanation: The longest increasing subsequences are [2, 3, 7, 18], [2, 5, 7, 18], [2, 3, 101], and [2, 5, 101], each having a length of 4. Thus, there are four such subsequences.

3. Example 3:

   • Input: nums = [1, 5, 2, 6, 3, 7]
   • Expected Output: 3
   • Explanation: The longest increasing subsequences are [1, 2, 3, 7], [1, 2, 6, 7], and [1, 5, 6, 7].

Constraints:

• 1 <= nums.length <= 2000
• -10⁶ <= nums[i] <= 10⁶

Solution

To solve this problem, the Binary Indexed Tree (BIT) algorithm is a great choice due to its efficiency in handling prefix sums and updates. The key idea is to maintain a frequency and length count for subsequences ending at each index of the array. Using BIT allows us to efficiently calculate and update the number of valid subsequences that can be extended by adding the current number.

This approach works because BIT efficiently tracks cumulative sums and updates in logarithmic time, which is crucial for handling the dynamic nature of the problem. Given that we need to frequently update and query subsequence lengths, BIT ensures that these operations are performed quickly, making it a suitable and effective approach for solving this problem.

Step-by-Step Algorithm

1. Initialize Variables:

   • n: Store the size of the input array Nums.
   • nums: Copy the input array Nums to use in sorting.
   • bit: Initialize a list of BITNode objects (Binary Indexed Tree), each holding maxLength and frequency.

2. Create and Sort Index List:

   • Indices: Create a list of indices [0, 1, 2, ..., n-1] corresponding to elements in nums.
   • Sort Indices: Sort Indices based on values in nums. If two elements are equal, prioritize the one with the higher index.
     • Sorting ensures that we process elements in increasing order. This helps us efficiently calculate and update the longest increasing subsequence up to each element.

3. Process Each Element:

   • Loop through each index in the sorted list:
     • Get Maximum Length: Use getMax(index) to find the maximum length of the LIS that ends before the current index.
     • Check for New Subsequence:
       • If maxLength == 0, start a new subsequence by calling update(index, 1, 1).
     • Update BIT:
       • If maxLength > 0, find the frequency of subsequences with this length using getFrequency(index, maxLength).
       • Call update(index, maxLength + 1, frequency) to record a new subsequence with updated length and frequency.

4. BIT Operations:

   • getMax(index):
     • Starts at index + 1 and moves upwards through the BIT by subtracting the last set bit (index -= index & -index).
     • During each step, it checks the maxLength stored at the current position in the BIT and updates the result with the maximum value found.
     • Returns the maximum length of any LIS that ends before the given index.
   • getFrequency(index, maxLength):
     • Similar to getMax, it starts at index + 1 and moves upwards through the BIT.
     • During each step, it checks if the maxLength at the current position matches the target maxLength. If it does, the corresponding frequency is added to the result.
     • Returns the total count of LIS with the given maxLength that ends before the specified index.
   • update(index, maxLength, frequency):
     • Starts at index + 1 and moves downwards through the BIT by adding the last set bit (index += index & -index).
     • At each step, it compares the maxLength at the current position:
       • If the stored maxLength is less than the current maxLength, it updates both maxLength and frequency.
       • If the stored maxLength is equal to the current maxLength, it adds the frequency to the existing value.
     • This operation updates the BIT to reflect the new subsequence information at the given index.

5. Final Result:

   • Find the maximum length of any LIS in the array using getMax(n-1).
   • Get the total number of LIS with this maximum length using getFrequency(n-1, maxLength).
   • Return this frequency as the result.

Algorithm Walkthrough

Input: nums = [2, 6, 4, 3, 5]

1. Initialization:

   • Input: nums = [2, 6, 4, 3, 5]
   • Length n = 5.
   • bit: A list of 6 BITNode objects, each initialized with maxLength = 0 and frequency = 0.

2. Create and Sort Index List:

   • Indices = [0, 1, 2, 3, 4] (indices of nums).
   • After sorting indices using custom comparator cmp, based on values in nums:
     • Indices = [0, 3, 2, 4, 1]
     • Values at these indices: [2, 3, 4, 5, 6].

3. Process Each Element:

   • Index 0 (nums[0] = 2):

     • Get Maximum Length (getMax(0)):
       • Start at index 1 (index + 1).
       • Traverse BIT: Check position 1 (0), position 0 (stop).
       • Result: maxLength = 0.
     • Since maxLength == 0, start a new subsequence:
     • Update BIT (update(0, 1, 1)):
       • Start at index 1.
       • Traverse BIT: Update position 1 (1,1), position 2 (1,1), position 4 (1,1).
       • BIT after update: [0, (1,1), (1,1), (0,0), (1,1), (0,0)].

   • Index 3 (nums[3] = 3):

     • Get Maximum Length (getMax(3)):
       • Start at index 4 (index + 1).
       • Traverse BIT: Check position 4 (1), position 0 (stop).
       • Result: maxLength = 1.
     • Get Frequency (getFrequency(3, 1)):
       • Start at index 4.
       • Traverse BIT: Check position 4 (1), position 0 (stop).
       • Result: frequency = 1.
     • Update BIT (update(3, 2, 1)):
       • Start at index 4.
       • Traverse BIT: Update position 4 (2,1), position 8 (stop).
       • BIT after update: [0, (1,1), (1,1), (0,0), (2,1), (0,0)].

   • Index 2 (nums[2] = 4):

     • Get Maximum Length (getMax(2)):
       • Start at index 3 (index + 1).
       • Traverse BIT: Check position 3 (0), position 2 (1), position 0 (stop).
       • Result: maxLength = 1.
     • Get Frequency (getFrequency(2, 1)):
       • Start at index 3.
       • Traverse BIT: Check position 3 (0), position 2 (1), position 0 (stop).
       • Result: frequency = 1.
     • Update BIT (update(2, 2, 1)):
       • Start at index 3.
       • Traverse BIT: Update position 3 (2,1), position 4 (2,2), position 8 (stop).
       • BIT after update: [0, (1,1), (1,1), (2,1), (2,2), (0,0)].

   • Index 4 (nums[4] = 5):

     • Get Maximum Length (getMax(4)):
       • Start at index 5 (index + 1).
       • Traverse BIT: Check position 5 (0), position 4 (2), position 0 (stop).
       • Result: maxLength = 2.
     • Get Frequency (getFrequency(4, 2)):
       • Start at index 5.
       • Traverse BIT: Check position 5 (0), position 4 (2), position 0 (stop).
       • Result: frequency = 2.
     • Update BIT (update(4, 3, 2)):
       • Start at index 5.
       • Traverse BIT: Update position 5 (3,2), position 6 (stop).
       • BIT after update: [0, (1,1), (1,1), (2,1), (2,2), (3,2)].

   • Index 1 (nums[1] = 6):

     • Get Maximum Length (getMax(1)):
       • Start at index 2 (index + 1).
       • Traverse BIT: Check position 2 (1), position 0 (stop).
       • Result: maxLength = 1.
     • Get Frequency (getFrequency(1, 1)):
       • Start at index 2.
       • Traverse BIT: Check position 2 (1), position 0 (stop).
       • Result: frequency = 1.
     • Update BIT (update(1, 4, 2)):
       • Start at index 2.
       • Traverse BIT: Update position 2 (2,1), position 4 (2,3), position 6 (stop).
       • BIT after update: [0, (1,1), (2,1), (2,1), (2,3), (3,2)].

4. Final Result:

   • Get Maximum Length (getMax(4)):
     • Start at index 5 (index + 1).
     • Traverse BIT: Check position 5 (2), position 4 (3), position 0 (stop).
     • Result: maxLength = 3.
   • Get Frequency (getFrequency(4, 3)):
     • Start at index 5.
     • Traverse BIT: Check position 4 (2), position 0 (stop).
     • Result: frequency = 2.
   • Final Result: Return 2 as the number of longest increasing subsequences.

Code

Complexity Analysis

Time Complexity

• Sorting the indices takes O(n log n).
• For each index in the sorted list, the algorithm performs two operations:
  • Getting the maximum length: This operation is O(log n) since it traverses the Binary Indexed Tree.
  • Getting the frequency: This is also O(log n) for the same reason.
  • Updating the BIT: The update operation is O(log n) as well.
• Since these operations are performed for each element in the array, the overall time complexity is O(n log n).

Space Complexity

• The space complexity is O(n) because of the additional space required for the BIT and the sorted index list.
• The input array itself is O(n).