medium Number of Longest Increasing Subsequence

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

import java.util.*;

public class Solution {

  // Define a class to represent each node in the BIT
  class BITNode {

    int frequency; // frequency of subsequences
    int maxLength; // maximum length of increasing subsequence

    BITNode() {
      frequency = 0;
      maxLength = 0;
    }
  }

  private int n; // length of the input array
  private List<BITNode> bit; // Binary Indexed Tree (BIT) to store max lengths and frequencies
  private List<Integer> nums; // the input array

  // Comparator to sort indices based on values in nums and then by index
  private boolean cmp(int index1, int index2) {
    if (nums.get(index1) != nums.get(index2)) {
      return nums.get(index1) < nums.get(index2);
    }
    return index1 > index2;
  }

  public int findNumberOfLIS(List<Integer> Nums) {
    this.n = Nums.size(); // get the size of the input array
    this.nums = Nums; // store the input array

    // Create a list of indices
    List<Integer> indices = new ArrayList<>();
    for (int i = 0; i < n; i++) indices.add(i);

    // Sort indices using the custom comparator
    indices.sort((a, b) -> cmp(a, b) ? -1 : 1);

    // Initialize BIT with n+1 nodes
    bit = new ArrayList<>();
    for (int i = 0; i <= n; i++) bit.add(new BITNode());

    // Traverse through the sorted indices
    for (int index : indices) {
      int maxLength = getMax(index); // Get max length of increasing subsequence ending before this index

      if (maxLength == 0) {
        // If no subsequence is found, start a new one
        update(index, 1, 1);
        continue;
      }

      int frequency = getFrequency(index, maxLength); // Get frequency of subsequences with max length
      update(index, maxLength + 1, frequency); // Update BIT with new max length and frequency
    }

    int maxLength = getMax(n - 1); // Get max length of increasing subsequence in the whole array
    return getFrequency(n - 1, maxLength); // Return the frequency of subsequences with max length
  }

  private int getMax(int index) {
    index++;
    int result = 0;
    while (index > 0) {
      result = Math.max(result, bit.get(index).maxLength); // Update result with the max length found
      index -= index & -index; // Move to the parent node
    }
    return result;
  }

  private int getFrequency(int index, int maxLength) {
    index++;
    int result = 0;
    while (index > 0) {
      if (bit.get(index).maxLength == maxLength) {
        result += bit.get(index).frequency; // Accumulate frequency of matching subsequences
      }
      index -= index & -index; // Move to the parent node
    }
    return result;
  }

  private void update(int index, int maxLength, int frequency) {
    index++;
    while (index <= n) {
      if (bit.get(index).maxLength < maxLength) {
        bit.get(index).maxLength = maxLength; // Update max length
        bit.get(index).frequency = frequency; // Set the frequency
      } else if (bit.get(index).maxLength == maxLength) {
        bit.get(index).frequency += frequency; // Increment frequency for existing max length
      }
      index += index & -index; // Move to the next node
    }
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    List<Integer> nums1 = Arrays.asList(2, 6, 4, 3, 5);
    int result1 = solution.findNumberOfLIS(nums1);
    System.out.println("Number of Longest Increasing Subsequences: " + result1); // Expected output: 2

    // Example 2
    List<Integer> nums2 = Arrays.asList(10, 9, 2, 5, 3, 7, 101, 18);
    int result2 = solution.findNumberOfLIS(nums2);
    System.out.println("Number of Longest Increasing Subsequences: " + result2); // Expected output: 4

    // Example 3
    List<Integer> nums3 = Arrays.asList(1, 5, 2, 6, 3, 7);
    int result3 = solution.findNumberOfLIS(nums3);
    System.out.println("Number of Longest Increasing Subsequences: " + result3); // Expected output: 3
  }
}

Complexity Analysis

Time Complexity

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

Space Complexity

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