# Number of Longest Increasing Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-longest-increasing-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/number-of-longest-increasing-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Binary Indexed Tree, Segment Tree
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Commvault](https://scaleengineer.com/companies/commvault)
---
## 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].

**Example 2:**

**Input:** nums = [2,2,2,2,2]
**Output:** 5
**Explanation:** The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

**Constraints:**

* `1 <= nums.length <= 2000`
* `-106 <= nums[i] <= 106`
* The answer is guaranteed to fit inside a 32-bit integer.

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. It maintains two arrays: one to track the length of the longest increasing subsequence (LIS) ending at each position, and another to track the count of such subsequences. By iterating through the array and comparing each element with all previous elements, it builds up the lengths and counts for all possible LIS.
**Time:** O(N^2), where N is the length of `nums`. The nested loops to compare each element with all its predecessors result in a quadratic runtime. · **Space:** O(N), where N is the length of `nums`. We use two arrays, `length` and `count`, of size N.
**Pros:** It is relatively straightforward to understand and implement.; The logic directly follows the definition of the problem.
**Cons:** The O(N^2) time complexity makes it slow for large input arrays, potentially leading to a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
In this method, we use two arrays, `length` and `count`, both of size `n`, where `n` is the length of the input array `nums`.

- `length[i]`: Stores the length of the longest increasing subsequence that ends with the element `nums[i]`.
- `count[i]`: Stores the number of distinct longest increasing subsequences that end with the element `nums[i]`.

We initialize `length[i]` and `count[i]` to `1` for all `i`, as any single element itself is an increasing subsequence of length 1.

We then iterate from the first element to the last. For each element `nums[i]`, we iterate through all previous elements `nums[j]` (where `j < i`). If `nums[i]` is strictly greater than `nums[j]`, it means we can extend an increasing subsequence ending at `j`. 

There are two cases:
1.  If extending the subsequence at `j` gives a longer subsequence for `i` (i.e., `length[j] + 1 > length[i]`), we've found a new maximum length for LIS ending at `i`. We update `length[i]` to this new length and set `count[i]` to be `count[j]`, because all the ways to form the LIS ending at `j` now extend to a new LIS ending at `i`.
2.  If extending the subsequence at `j` results in a subsequence of the same length as the current LIS for `i` (i.e., `length[j] + 1 == length[i]`), it means we've found an alternative way to form the LIS of that length. So, we add `count[j]` to `count[i]`.

After populating both arrays, we find the overall `maxLength` of any LIS by finding the maximum value in the `length` array. Finally, we sum up the `count[i]` for all indices `i` where `length[i]` equals `maxLength` to get the total number of longest increasing subsequences.

```java
import java.util.Arrays;

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return n;
        }
        // length[i] = length of LIS ending at nums[i]
        int[] length = new int[n]; 
        // count[i] = number of LIS ending at nums[i]
        int[] count = new int[n];  
        Arrays.fill(length, 1);
        Arrays.fill(count, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (length[j] + 1 > length[i]) {
                        length[i] = length[j] + 1;
                        count[i] = count[j]; // Reset count
                    } else if (length[j] + 1 == length[i]) {
                        count[i] += count[j]; // Add ways
                    }
                }
            }
        }

        int maxLength = 0;
        for (int len : length) {
            maxLength = Math.max(maxLength, len);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            if (length[i] == maxLength) {
                result += count[i];
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize two arrays, `length` and `count`, of size `n` (the length of `nums`), and fill them with `1`.
- `length[i]` will store the length of the longest increasing subsequence (LIS) ending at index `i`.
- `count[i]` will store the number of such LIS ending at index `i`.
- Iterate through the `nums` array with an outer loop from `i = 0` to `n-1`.
- Inside, have a nested loop from `j = 0` to `i-1`.
- If `nums[i] > nums[j]`, we can extend the subsequence ending at `j`.
  - If `length[j] + 1 > length[i]`, we have found a new, longer LIS ending at `i`. Update `length[i] = length[j] + 1` and reset `count[i] = count[j]`.
  - If `length[j] + 1 == length[i]`, we have found another way to form an LIS of the same length. We add the counts: `count[i] += count[j]`.
- After the loops, find the maximum length (`maxLength`) in the `length` array.
- Iterate through the `length` array one last time. Sum up all `count[i]` where `length[i]` is equal to `maxLength`.
- Return the final sum.

## Segment Tree with Coordinate Compression
This advanced approach optimizes the O(N^2) DP solution to O(N log N) using a Segment Tree (or a Fenwick Tree) combined with coordinate compression. The core idea is to replace the linear scan for previous subsequences with an efficient logarithmic time query on a data structure. The Segment Tree stores information about the lengths and counts of LIS ending at various values, allowing for quick retrieval of the necessary data to extend a subsequence.
**Time:** O(N log N), where N is the length of `nums`. Coordinate compression takes O(N log N). The main loop runs N times, and each iteration involves a query and an update on the Segment Tree, both of which take O(log M) time, where M is the number of unique elements (M <= N). · **Space:** O(N), where N is the length of `nums`. The space is used for coordinate compression (map and set) and the Segment Tree. In the worst case (all unique elements), the tree can have O(N) nodes.
**Pros:** Highly efficient with O(N log N) time complexity, making it suitable for large datasets.; Demonstrates a powerful technique combining data structures and dynamic programming.
**Cons:** The implementation is significantly more complex than the DP approach, requiring knowledge of Segment Trees (or Fenwick Trees) and coordinate compression.; The constant factors in the time complexity might be higher than the DP approach for very small N.
### Explanation
The O(N^2) DP approach is bottlenecked by the inner loop, which performs a linear scan to find the best previous subsequence to extend. We can optimize this search from O(N) to O(log N) using a data structure like a Segment Tree.

**1. Coordinate Compression:**
The values in `nums` can be large, but their exact values don't matter as much as their relative order. We can map each unique number in `nums` to a smaller integer rank (from `0` to `m-1`, where `m` is the number of unique elements). This step takes O(N log N) due to sorting.

**2. Segment Tree:**
We use a Segment Tree built over the range of these ranks. Each node in the tree will store a `Pair` object containing `(length, count)`. This pair represents the maximum LIS length found within the node's range and the number of ways to achieve it.

We define a `combine` function to merge the results from two nodes. When combining `(l1, c1)` and `(l2, c2)`:
- If `l1 > l2`, the result is `(l1, c1)`. 
- If `l2 > l1`, the result is `(l2, c2)`.
- If `l1 == l2`, the result is `(l1, c1 + c2)`.

**3. Algorithm Flow:**
We iterate through each number `num` in the original `nums` array.
- For each `num`, we find its rank, `r`.
- We query our Segment Tree on the range `[0, r-1]`. This query uses the `combine` function to find the best `(length, count)` pair among all subsequences that could precede `num` (i.e., those ending with a value smaller than `num`). Let's say this query returns `(prevLen, prevCount)`. A query on an empty range should logically return `(0, 1)` to represent the empty subsequence which has length 0 and 1 way to form.
- The new LIS ending with `num` will have length `newLen = prevLen + 1` and count `newCount = prevCount`.
- We then update the Segment Tree at the position `r` with this new `(newLen, newCount)` pair. The update also uses the `combine` logic to handle cases where multiple numbers have the same value.

After iterating through all numbers, the final answer is the `count` from the pair stored at the root of the Segment Tree, which represents the combined result over the entire range of ranks.

```java
import java.util.*;

class Solution {
    // A pair to store (length, count)
    class Pair {
        int length;
        int count;
        Pair(int length, int count) {
            this.length = length;
            this.count = count;
        }
    }

    // Segment Tree Node
    class Node {
        Pair pair;
        Node left, right;
        Node() {
            this.pair = new Pair(0, 0);
            this.left = null;
            this.right = null;
        }
    }

    // Combine function for two pairs
    private Pair combine(Pair p1, Pair p2) {
        if (p1.length > p2.length) return p1;
        if (p2.length > p1.length) return p2;
        return new Pair(p1.length, p1.count + p2.count);
    }

    // Update operation on the segment tree (implicit/dynamic)
    private void update(Node node, int start, int end, int index, Pair value) {
        if (start == end) {
            node.pair = combine(node.pair, value);
            return;
        }
        int mid = start + (end - start) / 2;
        if (index <= mid) {
            if (node.left == null) node.left = new Node();
            update(node.left, start, mid, index, value);
        } else {
            if (node.right == null) node.right = new Node();
            update(node.right, mid + 1, end, index, value);
        }
        Pair leftPair = (node.left != null) ? node.left.pair : new Pair(0, 0);
        Pair rightPair = (node.right != null) ? node.right.pair : new Pair(0, 0);
        node.pair = combine(leftPair, rightPair);
    }

    // Query operation on the segment tree
    private Pair query(Node node, int start, int end, int l, int r) {
        if (node == null || r < start || l > end || l > r) {
            return new Pair(0, 0);
        }
        if (l <= start && end <= r) {
            return node.pair;
        }
        int mid = start + (end - start) / 2;
        Pair leftResult = query(node.left, start, mid, l, r);
        Pair rightResult = query(node.right, mid + 1, end, l, r);
        return combine(leftResult, rightResult);
    }

    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // Coordinate Compression
        Set<Integer> uniqueNums = new TreeSet<>();
        for (int num : nums) {
            uniqueNums.add(num);
        }
        Map<Integer, Integer> rankMap = new HashMap<>();
        int rank = 0;
        for (int num : uniqueNums) {
            rankMap.put(num, rank++);
        }

        int maxRank = rank - 1;
        Node root = new Node();

        for (int num : nums) {
            int currentRank = rankMap.get(num);
            // Query for LIS ending with a value smaller than num
            Pair result = query(root, 0, maxRank, 0, currentRank - 1);
            
            // If no smaller element, LIS is of length 1, count 1
            if (result.length == 0) {
                result = new Pair(0, 1);
            }

            int newLength = result.length + 1;
            int newCount = result.count;

            // Update the tree with the new LIS info for the current number
            update(root, 0, maxRank, currentRank, new Pair(newLength, newCount));
        }

        return root.pair.count;
    }
}
```
### Algorithm
- **Coordinate Compression**: First, handle the potentially large range of numbers in `nums`. Create a sorted list of unique values from `nums` and map each value to a rank (a small integer). This reduces the problem's value space to at most `N`.
- **Segment Tree Setup**: Initialize a Segment Tree over the range of ranks. Each node in the tree will store a pair `(length, count)`, representing the LIS length and the number of ways to achieve it within that node's range. A `combine` function is needed to merge pairs from child nodes: if lengths differ, take the pair with the greater length; if lengths are equal, sum their counts.
- **Processing Elements**: Iterate through each `num` in the input array `nums`.
  - Get the rank `r` of `num` from the map created earlier.
  - Query the Segment Tree for the range of ranks `[0, r-1]`. This efficiently finds the `(maxLength, count)` pair for all LIS ending with a value smaller than `num`. Let the result be `(prevLen, prevCount)`. The base case for an empty range query is `(0, 1)` (for an empty subsequence).
  - The LIS ending with the current `num` will have length `newLen = prevLen + 1` and count `newCount = prevCount`.
  - Update the Segment Tree at rank `r` with this new pair `(newLen, newCount)`, using the `combine` logic to merge with any existing data at that rank (for handling duplicate numbers).
- **Final Result**: After processing all numbers, the final answer is the `count` part of the pair returned by querying the entire range of ranks in the Segment Tree.

# Solutions
### Java

```java
class BinaryIndexedTree { private int n ; private int [] c ; private int [] d ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; d = new int [ n + 1 ]; } public void update ( int x , int v , int cnt ) { while ( x <= n ) { if ( c [ x ] < v ) { c [ x ] = v ; d [ x ] = cnt ; } else if ( c [ x ] == v ) { d [ x ] += cnt ; } x += x & - x ; } } public int [] query ( int x ) { int v = 0 , cnt = 0 ; while ( x > 0 ) { if ( c [ x ] > v ) { v = c [ x ]; cnt = d [ x ]; } else if ( c [ x ] == v ) { cnt += d [ x ]; } x -= x & - x ; } return new int [] { v , cnt }; } } public class Solution { public int findNumberOfLIS ( int [] nums ) { // int[] arr = Arrays.stream(nums).distinct().sorted().toArray(); int [] arr = nums . clone (); Arrays . sort ( arr ); int m = arr . length ; BinaryIndexedTree tree = new BinaryIndexedTree ( m ); for ( int x : nums ) { int i = Arrays . binarySearch ( arr , x ) + 1 ; int [] t = tree . query ( i - 1 ); int v = t [ 0 ]; int cnt = t [ 1 ]; tree . update ( i , v + 1 , Math . max ( cnt , 1 )); } return tree . query ( m )[ 1 ]; } }
```

### CPP

```cpp
class BinaryIndexedTree { private: int n ; vector < int > c ; vector < int > d ; public: BinaryIndexedTree ( int n ) : n ( n ) , c ( n + 1 , 0 ) , d ( n + 1 , 0 ) {} void update ( int x , int v , int cnt ) { while ( x <= n ) { if ( c [ x ] < v ) { c [ x ] = v ; d [ x ] = cnt ; } else if ( c [ x ] == v ) { d [ x ] += cnt ; } x += x & - x ; } } pair < int , int > query ( int x ) { int v = 0 , cnt = 0 ; while ( x > 0 ) { if ( c [ x ] > v ) { v = c [ x ]; cnt = d [ x ]; } else if ( c [ x ] == v ) { cnt += d [ x ]; } x -= x & - x ; } return { v , cnt }; } }; class Solution { public: int findNumberOfLIS ( vector < int >& nums ) { vector < int > arr = nums ; sort ( arr . begin (), arr . end ()); arr . erase ( unique ( arr . begin (), arr . end ()), arr . end ()); int m = arr . size (); BinaryIndexedTree tree ( m ); for ( int x : nums ) { auto it = lower_bound ( arr . begin (), arr . end (), x ); int i = distance ( arr . begin (), it ) + 1 ; auto [ v , cnt ] = tree . query ( i - 1 ); tree . update ( i , v + 1 , max ( cnt , 1 )); } return tree . query ( m ). second ; } };
```

### Python

```python
class BinaryIndexedTree : __slots__ = [ "n" , "c" , "d" ] def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) self . d = [ 0 ] * ( n + 1 ) def update ( self , x , v , cnt ): while x <= self . n : if self . c [ x ] < v : self . c [ x ] = v self . d [ x ] = cnt elif self . c [ x ] == v : self . d [ x ] += cnt x += x & - x def query ( self , x ): v = cnt = 0 while x : if self . c [ x ] > v : v = self . c [ x ] cnt = self . d [ x ] elif self . c [ x ] == v : cnt += self . d [ x ] x -= x & - x return v , cnt class Solution : def findNumberOfLIS ( self , nums : List [ int ]) -> int : arr = sorted ( set ( nums )) m = len ( arr ) tree = BinaryIndexedTree ( m ) for x in nums : i = bisect_left ( arr , x ) + 1 v , cnt = tree . query ( i - 1 ) tree . update ( i , v + 1 , max ( cnt , 1 )) return tree . query ( m )[ 1 ]
```