Number of Longest Increasing Subsequence

MediumDynamic Programming · LIS · Fenwick Tree🧩 Longest Increasing Subsequence LeetCode #673 ↗Updated Oct 30, 2026

Problem

Given an integer array nums, find the length L of its longest strictly increasing subsequence, and return how many different subsequences have length L. Subsequences are distinguished by the indices they use, so equal values at different positions count separately.

Inputnums = [1,3,5,4,7]Output2 ([1,3,5,7] and [1,3,4,7])

Inputnums = [2,2,2,2,2]Output5 (each single element)

1 ≤ n ≤ 2000 · -10⁶ ≤ nums[i] ≤ 10⁶ · the answer fits in a 32-bit int

Try it yourself

Java

class Solution {
    public int findNumberOfLIS(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Track two numbers per index: len[i], the longest increasing run ending at i, and cnt[i], how many runs reach that length. When extending from j, a longer length replaces the count; an equal length adds to it.

PatternLongest Increasing Subsequence

Instinct Longest chain where each pick must beat the last (bigger, later, fits inside) - O(n²) best-ending-here DP, or O(n log n) tails plus binary search.

Memory hack Patience solitaire - drop each card on the leftmost pile whose top is not smaller; the number of piles is the LIS length.

Open the Longest Increasing Subsequence guide →

Approaches

Brute ForceRecursion: Longest Runs Starting at Each Index

Time O(n · 2ⁿ)Space O(n)

For a start index i, recursively try every next index j > i with a bigger value and combine the children's (length, count) pairs: keep the longest, summing counts on ties. Without caching, every increasing subsequence is walked separately.

Java

public int findNumberOfLIS(int[] nums) {
    int bestLen = 0, total = 0;
    for (int i = 0; i < nums.length; i++) {
        int[] r = longestFrom(nums, i);
        if (r[0] > bestLen) { bestLen = r[0]; total = r[1]; }
        else if (r[0] == bestLen) total += r[1];
    }
    return total;
}

// {length, count} of the longest increasing subsequences starting at i
private int[] longestFrom(int[] nums, int i) {
    int len = 1, cnt = 1;
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] <= nums[i]) continue;
        int[] r = longestFrom(nums, j);
        if (r[0] + 1 > len) { len = r[0] + 1; cnt = r[1]; }
        else if (r[0] + 1 == len) cnt += r[1];
    }
    return new int[]{len, cnt};
}

Shows the (length, count) combine rule, but is exponential.

BetterO(n²) DP with Length and Count Arrays

Time O(n²)Space O(n)

Process indices left to right. For each i, look at every earlier j with nums[j] < nums[i]: len[j]+1 is a candidate length with cnt[j] ways. Finally sum cnt over all indices whose len equals the global maximum.

Java

public int findNumberOfLIS(int[] nums) {
    int n = nums.length;
    int[] len = new int[n]; // longest run ending at i
    int[] cnt = new int[n]; // number of such runs
    int bestLen = 0, total = 0;
    for (int i = 0; i < n; i++) {
        len[i] = 1;
        cnt[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] >= nums[i]) continue;
            if (len[j] + 1 > len[i]) {
                len[i] = len[j] + 1;
                cnt[i] = cnt[j];          // strictly longer: reset count
            } else if (len[j] + 1 == len[i]) {
                cnt[i] += cnt[j];         // tie: add ways
            }
        }
        if (len[i] > bestLen) { bestLen = len[i]; total = cnt[i]; }
        else if (len[i] == bestLen) total += cnt[i];
    }
    return total;
}

Dry runnums = [1,3,5,4,7]

i current index (cell = len/cnt) changed

i=0
1/1
i
·

·

·

·

nums=[1,3,5,4,7]
i=1
1/1

2/1
i
·

·

·

from 1
i=2
1/1

2/1

3/1
i
·

·

from 3
i=3
1/1

2/1

3/1

3/1
i
·

4: from 3, not 5
i=4
1/1

2/1

3/1

3/1

4/2
i
ties 5 & 4 → 2 ✔

The standard interview answer; 4·10⁶ steps at n = 2000.

OptimalFenwick Tree of (length, count) over Value Ranks

Time O(n log n)Space O(n)

The inner loop of the DP asks: “among values smaller than nums[i] seen so far, what is the best length and its total count?” That is a prefix query over values. Compress values to ranks and keep a Fenwick tree whose nodes store the combined (max length, count) of their range.

Java

private int[] tLen, tCnt;

public int findNumberOfLIS(int[] nums) {
    int[] vals = nums.clone();
    Arrays.sort(vals);
    int m = 0; // number of distinct values
    for (int v : vals) if (m == 0 || vals[m - 1] != v) vals[m++] = v;
    tLen = new int[m + 1];
    tCnt = new int[m + 1];
    for (int x : nums) {
        int rank = Arrays.binarySearch(vals, 0, m, x) + 1; // 1-based
        int[] best = query(rank - 1);  // strictly smaller values
        int len = best[0] + 1;
        int cnt = best[0] == 0 ? 1 : best[1];
        for (int i = rank; i <= m; i += i & -i) {
            if (len > tLen[i]) { tLen[i] = len; tCnt[i] = cnt; }
            else if (len == tLen[i]) tCnt[i] += cnt;
        }
    }
    return query(m)[1];
}

// combined {max length, count} over ranks 1..i
private int[] query(int i) {
    int len = 0, cnt = 0;
    for (; i > 0; i -= i & -i) {
        if (tLen[i] > len) { len = tLen[i]; cnt = tCnt[i]; }
        else if (tLen[i] == len) cnt += tCnt[i];
    }
    return new int[]{len, cnt};
}

Log-time per element; worth it if n grows far beyond 2000.

Pro tip

Query rank r-1, not r — equal values must not extend each other (strictly increasing).

At a glance

Level	Approach	Time	Space
Brute Force	Recursion: Longest Runs Starting at Each Index	`O(n · 2ⁿ)`	`O(n)`
Better	O(n²) DP with Length and Count Arrays	`O(n²)`	`O(n)`
Optimal	Fenwick Tree of (length, count) over Value Ranks	`O(n log n)`	`O(n)`

Common pitfalls

Returning cnt of the last index only — sum over every index with the max length.
On a strictly longer extension, assign cnt[i] = cnt[j]; adding double-counts.
Using ≤ instead of < lets equal values chain together.

Interview tips

Start from classic LIS and say: “I just need a count alongside each length.”
Walk the tie-vs-longer rule on [1,3,5,4,7] — it convinces quickly.
Mention the Fenwick/segment-tree upgrade only after the O(n²) version is correct.

Pattern

LIS DP with counting → when you need how many optimal subsequences, not just the optimal length.

My notes saved in this browser