Number of Longest Increasing Subsequences — DP, Segment Tree & BIT Solutions

Problem Statement#

LeetCode 673 — Number of Longest Increasing Subsequence | Difficulty: Medium

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

Constraints:

• 1 is less than or equal to nums.length, which is less than or equal to 2000
• -10^6 is less than or equal to nums[i], which is less than or equal to 10^6

Example 1:

Input:  nums = [1, 3, 5, 4, 7]
Output: 2
Explanation:
  Two LIS of length 4: [1,3,5,7] and [1,3,4,7]

Example 2:

Input:  nums = [2, 2, 2, 2, 2]
Output: 5
Explanation:
  Length 1 is the longest strictly increasing run; each element is one LIS.

Why This Problem Matters#

Number of LIS is the canonical interview problem for DP enriched with counts. Google, Amazon, and Meta rotate it because it requires you to extend the standard O(n^2) LIS DP with a second dimension — the count of subsequences achieving the optimal length — and then optionally upgrade to O(n log n) with a segment tree on values.

This pattern appears anywhere you need both an extremal value and the multiplicity of paths reaching it: counting shortest paths in graphs, counting maximum matchings, scoring optimal alignments in bioinformatics. Mastering the (length, count) pairing here unlocks an entire class of problems.

The Core Insight#

For each index i, store two values:

• length[i] — the length of the longest strictly increasing subsequence ending at index i
• count[i] — the number of distinct LIS of that length ending at i

DP transition. For each i, look at every j less than i with nums[j] less than nums[i]:

• If length[j] + 1 is greater than length[i]: we found a strictly longer LIS ending at i. Set length[i] = length[j] + 1 and count[i] = count[j] (overwrite — every LIS ending at j extends uniquely).
• Else if length[j] + 1 equals length[i]: we tied the current best length via a different j. Add count[j] to count[i].
• Else: shorter, ignore.

Initialization. length[i] = 1, count[i] = 1 (singleton subsequence).

Answer. Find max_len = max(length). Sum count[i] over all i with length[i] = max_len.

This naive DP is O(n^2). For larger n, replace the inner loop with a segment tree on coordinate-compressed values that returns (best_length, total_count) for all values strictly less than nums[i]. That gives O(n log n).

Visual Dry Run#

Trace nums = [1, 3, 5, 4, 7] with the O(n^2) DP.

Init:  length = [1, 1, 1, 1, 1]
       count  = [1, 1, 1, 1, 1]
 
i=1, nums[1]=3:
  j=0: nums[0]=1 < 3, length[0]+1=2 > length[1]=1 -> length[1]=2, count[1]=count[0]=1
 
i=2, nums[2]=5:
  j=0: 1<5, 1+1=2 > 1 -> length[2]=2, count[2]=1
  j=1: 3<5, 2+1=3 > 2 -> length[2]=3, count[2]=count[1]=1
 
i=3, nums[3]=4:
  j=0: 1<4, 2 > 1 -> length[3]=2, count[3]=1
  j=1: 3<4, 3 > 2 -> length[3]=3, count[3]=count[1]=1
  j=2: 5<4? no -> skip
 
i=4, nums[4]=7:
  j=0: 1<7, 2 > 1 -> length[4]=2, count[4]=1
  j=1: 3<7, 3 > 2 -> length[4]=3, count[4]=1
  j=2: 5<7, 4 > 3 -> length[4]=4, count[4]=count[2]=1
  j=3: 4<7, 4 == 4 -> tie, count[4] += count[3] = 1+1 = 2

Final state:

max_len = 4. Sum of count[i] where length[i] = 4 is count[4] = 2. Answer: 2.

The two LIS of length 4 are [1,3,5,7] and [1,3,4,7].

Solution (Optimal)#

Python — O(n^2) DP#

from typing import List
 
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        length = [1] * n                                  # LIS length ending at i
        count = [1] * n                                   # number of such LIS
 
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:                     # strictly increasing
                    if length[j] + 1 > length[i]:         # found a longer LIS
                        length[i] = length[j] + 1
                        count[i] = count[j]               # adopt count from j
                    elif length[j] + 1 == length[i]:      # tied length, accumulate counts
                        count[i] += count[j]
 
        max_len = max(length)
        return sum(c for l, c in zip(length, count) if l == max_len)

Python — O(n log n) Segment Tree on Compressed Values#

from typing import List
 
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # coordinate compress values to dense ranks [1..k]
        sorted_unique = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
        size = len(sorted_unique)
 
        # segment tree node stores (max_length, total_count) for ranks in its range
        tree = [(0, 0)] * (4 * size)
 
        def merge(a, b):
            # combine two (length, count) pairs: keep larger length, sum counts on tie
            la, ca = a; lb, cb = b
            if la > lb: return (la, ca)
            if lb > la: return (lb, cb)
            return (la, ca + cb)
 
        def update(node, l, r, pos, val):
            if l == r:
                tree[node] = merge(tree[node], val)
                return
            mid = (l + r) // 2
            if pos <= mid: update(2 * node, l, mid, pos, val)
            else: update(2 * node + 1, mid + 1, r, pos, val)
            tree[node] = merge(tree[2 * node], tree[2 * node + 1])
 
        def query(node, l, r, ql, qr):
            if qr < l or r < ql: return (0, 0)
            if ql <= l and r <= qr: return tree[node]
            mid = (l + r) // 2
            return merge(query(2 * node, l, mid, ql, qr),
                         query(2 * node + 1, mid + 1, r, ql, qr))
 
        # process left to right; query ranks [1..r-1] then insert (length+1, count) at rank r
        for x in nums:
            r = rank[x]
            best_len, best_cnt = query(1, 1, size, 1, r - 1) if r > 1 else (0, 0)
            new_len = best_len + 1
            new_cnt = best_cnt if best_cnt > 0 else 1
            update(1, 1, size, r, (new_len, new_cnt))
 
        return tree[1][1] if tree[1][0] > 0 else len(nums)

JavaScript — O(n^2) DP#

var findNumberOfLIS = function(nums) {
    const n = nums.length;
    const length = new Array(n).fill(1);                 // LIS length at i
    const count = new Array(n).fill(1);                  // count of LIS at i
 
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {                     // strictly increasing
                if (length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                    count[i] = count[j];                 // overwrite count
                } else if (length[j] + 1 === length[i]) {
                    count[i] += count[j];                // accumulate count on tie
                }
            }
        }
    }
 
    const maxLen = Math.max(...length);
    let total = 0;
    for (let i = 0; i < n; i++) {
        if (length[i] === maxLen) total += count[i];
    }
    return total;
};

Complexity: DP solution: O(n^2) time, O(n) space — fine for n at 2000. Segment tree solution: O(n log n) time, O(n) space.

Common Mistakes#

1. Overwriting count on a tie. When length[j] + 1 equals length[i], you must add count[j] to count[i], not overwrite. Overwriting silently loses paths.
2. Using non-strict comparison. The problem requires strictly increasing. Using nums[j] <= nums[i] would count the duplicates incorrectly — the test case [2,2,2,2,2] exposes this immediately.
3. Initializing count[i] = 0. A single-element subsequence still has count 1. Both arrays initialize to 1.
4. Computing max_len incrementally and missing later updates. Track max_len after the full DP completes, or maintain it carefully alongside updates.
5. Wrong merge function for the segment tree. When combining two child intervals, you keep the larger length and sum counts only on tie. Summing counts always gives wrong totals.
6. Forgetting the r - 1 upper bound when querying. You query strictly smaller ranks, so the range is [1, r - 1]. Querying [1, r] includes equal values and breaks strictness.

Interview Tips#

• Open with the (length, count) pairing. "Standard LIS DP gives the length; I will track a parallel count array to handle multiplicity." Naming the augmentation up front earns credit.
• Test on a duplicates example. Walking [2,2,2,2,2] shows you respect the strictness condition.
• Mention the segment tree upgrade. "DP is O(n^2) which is fine for n at 2000; for larger n I would replace the inner loop with a segment tree on compressed values returning (max_length, count_at_max)." This shows breadth without forcing complexity.
• Show the merge function. Senior candidates often skip explaining how two segment-tree node payloads combine. Doing it clearly differentiates you.
• Discuss the O(n log n) LIS algorithm with patience sorting. Standard LIS uses a sorted "tails" array. Explain why patience sorting alone does not give counts — that is why we need the segment tree.

Follow-up Questions#

1. Number of Longest Common Subsequences. 2D DP with the same length-count pairing.
2. Number of strictly decreasing LIS. Reverse the comparison or reverse the array.
3. k-th LIS (lexicographically smallest). Augment with parent pointers and reconstruct.
4. Online insertions update the count. Use the segment tree variant; each new element triggers one query plus one update.
5. Distributed across shards. Sort by value globally, sweep with a single Fenwick or segment tree across the merge — same idea as merge-sort-on-prefix-sums.
6. Number of LIS in a 2D matrix (path-based). Topological order on cells; same DP per cell.

Key Takeaways#

• Track two parallel arrays — length[i] (best length ending at i) and count[i] (multiplicity of that length) — to count optimal subsequences via DP.
• On a strict improvement, overwrite the count; on a tie, accumulate counts.
• Initialize both arrays to 1 because a single element is a valid LIS of length 1.
• The O(n^2) DP suffices for n at 2000; upgrade to a segment tree on coordinate-compressed values for O(n log n) when n is large.
• The segment tree node payload is (max_length, total_count_at_max), with a custom merge that keeps the larger length and sums counts on tie.
• The (extreme value, count of paths) augmentation generalizes to shortest-path counting, optimal alignment counting, and many DP problems beyond LIS.