Number of Longest Increasing Subsequence: DP with Length and Count

May 21, 20266 min read

leetcodeproblemmediumarraysdynamic-programming

Given an unsorted array of integers, find the number of longest increasing subsequences. Not just the length of the longest one, but how many distinct subsequences achieve that maximum length.

This is LeetCode 673: Number of Longest Increasing Subsequence, and it builds directly on the classic Longest Increasing Subsequence problem. If you already know how to find the LIS length with DP, this problem asks you to extend that approach by also counting how many ways you can reach that length.

Array [1, 3, 5, 4, 7] has two longest increasing subsequences of length 4. Answer: 2.

Why counting matters

Finding the length of the LIS is a well-known DP problem. But counting how many subsequences share that maximum length requires tracking extra information at each index. You cannot just find the LIS length and then count backward. You need to accumulate counts as you go, because the number of ways to reach a given length at index i depends on the counts at all earlier indices that feed into it.

This is a common theme in DP problems: once you know how to optimize a value, the follow-up asks you to count the number of ways to achieve that optimum. The transition logic barely changes, but you need a second array to track the counts alongside the lengths.

The approach: two parallel DP arrays

The idea extends the classic LIS DP. Instead of maintaining just one array dp[i] for the length of the longest increasing subsequence ending at index i, you maintain two arrays:

lengths[i] = length of the longest increasing subsequence ending at index i
counts[i] = number of longest increasing subsequences of that length ending at index i

Both arrays start initialized to 1 (every element forms a subsequence of length 1, and there is exactly one such subsequence).

For each pair (j, i) where j is less than i and nums[j] is less than nums[i]:

If lengths[j] + 1 is greater than lengths[i], you found a strictly longer subsequence ending at i. Update lengths[i] = lengths[j] + 1 and reset counts[i] = counts[j] (all the ways to reach j now flow into i).
If lengths[j] + 1 equals lengths[i], you found another set of subsequences of the same best length. Add counts[j] to counts[i].

At the end, find the maximum value in lengths, then sum up counts[i] for every index where lengths[i] equals that maximum.

Practice this problem with spaced repetition

Brute force

The brute force approach generates all possible subsequences and checks which ones are increasing. For an array of length n, there are 2^n subsequences. For each one you verify whether it is strictly increasing and track the maximum length and count. This runs in O(2^n) time, which is far too slow for any practical input size.

Optimal solution

def find_number_of_lis(nums):
    n = len(nums)
    if n == 0:
        return 0

    lengths = [1] * n
    counts = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                if lengths[j] + 1 > lengths[i]:
                    lengths[i] = lengths[j] + 1
                    counts[i] = counts[j]
                elif lengths[j] + 1 == lengths[i]:
                    counts[i] += counts[j]

    max_len = max(lengths)
    return sum(c for l, c in zip(lengths, counts) if l == max_len)

The key logic is in the inner loop. For each candidate predecessor j, you either find a better length (and inherit that predecessor's count) or find an equal length (and accumulate that predecessor's count on top of what you already have). This is the only difference from standard LIS: one extra elif branch and a second array.

Walkthrough

Let's trace through the array [1, 3, 5, 4, 7] step by step. Watch how counts[4] ends up as 2 because two different predecessors (indices 2 and 3) each contribute one path of the same maximum length.

Step 1: Initialize both arrays

Every element is an increasing subsequence of length 1 by itself, and there is exactly 1 such subsequence at each position.

Step 2: i=1 (val 3). j=0: nums[0]=1 < 3, lengths[0]+1=2 > lengths[1]

Extending the subsequence [1] with 3. lengths[1]=2, counts[1]=counts[0]=1.

Step 3: i=2 (val 5). j=0 and j=1 both extend. Best is lengths[1]+1=3

From j=1: lengths[1]+1=3 > lengths[2]. Update lengths[2]=3, counts[2]=counts[1]=1. Subsequence: [1,3,5].

Step 4: i=3 (val 4). j=0,1 extend but NOT j=2 (5 > 4)

From j=1: lengths[1]+1=3 > lengths[3]. Update lengths[3]=3, counts[3]=counts[1]=1. Subsequence: [1,3,4]. Index 2 skipped since 5 > 4.

Step 5: i=4 (val 7). j=2 and j=3 both give length 4. Counts add up!

From j=2: lengths[2]+1=4, so lengths[4]=4, counts[4]=counts[2]=1. From j=3: lengths[3]+1=4 equals lengths[4], so counts[4]+=counts[3]=1+1=2.

Step 6: Result. Max length is 4, total count = counts[4] = 2

The longest increasing subsequence has length 4. Two subsequences achieve it: [1,3,5,7] and [1,3,4,7]. Answer: 2.

The crucial moment is step 5. When processing index 4 (value 7), both index 2 (value 5) and index 3 (value 4) produce lengths[j] + 1 = 4. The first one sets counts[4] = 1. The second one adds to it, giving counts[4] = 2. That final count of 2 is the answer: there are two longest increasing subsequences of length 4.

Build your pattern library with CodeBricks

Complexity analysis

Approach	Time	Space
Generate all subsequences	O(2^n)	O(n)
DP with length and count	O(n^2)	O(n)

The DP solution uses two arrays of length n and has a nested loop over all pairs, giving O(n^2) time and O(n) space. This is the same time complexity as standard LIS, just with a constant factor increase from maintaining the second array.

Edge cases to watch for

Empty array: return 0. There are no subsequences at all.
Single element: return 1. The only subsequence is the element itself.
All elements equal: e.g., [3, 3, 3]. Since the subsequence must be strictly increasing, every LIS has length 1, and every element is its own LIS. Answer equals n.
Strictly increasing array: e.g., [1, 2, 3, 4]. There is exactly one LIS (the entire array). Answer is 1.
Strictly decreasing array: e.g., [5, 4, 3, 2]. Every element is an LIS of length 1. Answer is n.
Multiple paths converging: the trickiest case. When several predecessors tie for the best length feeding into an index, you must sum all their counts rather than just taking the maximum.

The building blocks

This problem is built on linear DP with variable lookback, the same pattern used in the classic Longest Increasing Subsequence. The extension is a second DP array that tracks counts alongside lengths.

The "count the number of optimal solutions" pattern is reusable. Once you have a DP that computes an optimum, adding a count array follows the same template every time:

When you find a strictly better value, reset the count to match the source.
When you find an equal value, add the source count to the current count.

This pattern appears in several other problems:

Unique Paths (LeetCode 62): counting the number of ways to reach a cell, where each cell aggregates counts from its predecessors.
Longest Increasing Subsequence (LeetCode 300): the foundation this problem builds on.
Coin Change II (LeetCode 518): counting the number of combinations that sum to a target, another "count the ways" DP.

Once you recognize the "track optimum + count" template, problems like this become a mechanical extension of whichever DP you already know.

From understanding to recall

You have just traced through the complete DP for counting longest increasing subsequences. The logic is a small extension of standard LIS: one extra array and one extra branch in the inner loop. It is easy to understand when you see it laid out, but reproducing it under pressure requires having the pattern committed to memory.

The gap between following a walkthrough and writing the solution cold in an interview is real. Spaced repetition closes that gap. You revisit this problem at increasing intervals, write the two-array DP from scratch each time, and after a few reps the "count alongside optimize" pattern becomes automatic.

This counting-optimum DP template is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Longest Increasing Subsequence - The foundation this problem builds on, covering both O(n^2) DP and O(n log n) binary search
Maximum Product Subarray - Another DP problem where you track extra state (both max and min) alongside the primary value
Coin Change - Classic DP with variable lookback, same nested-loop structure applied to a different optimization target

Try CodeBricks free