LeetCode 673: Number of Longest Increasing Subsequence

Problem Restatement

We are given an integer array nums.

We need to return the number of longest increasing subsequences.

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

The subsequence must be strictly increasing. Equal adjacent values do not count as increasing. The official problem statement asks for the number of longest increasing subsequences and notes that the sequence must be strictly increasing.

Input and Output

Example function shape:

def findNumberOfLIS(nums: list[int]) -> int:
    ...

Examples

Consider:

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

The longest increasing subsequences have length 4.

They are:

1, 3, 5, 7
1, 3, 4, 7

So the answer is:

2

Another example:

nums = [2, 2, 2, 2, 2]

Since the sequence must be strictly increasing, no pair of equal values can be used together.

So the longest increasing subsequence length is 1.

Each single element is one valid subsequence.

There are five such subsequences, so the answer is:

5

First Thought: Generate All Subsequences

A direct solution is to generate every subsequence, check whether it is strictly increasing, and track the longest length and count.

This is too slow.

An array of length n has:

2^n

subsequences.

We need to avoid enumerating them.

Key Insight

This is a longest increasing subsequence problem, but we need both:

1. The best length.
2. The number of ways to achieve that length.

For each index i, store two values:

Every element can stand alone, so initially:

length[i] = 1
count[i] = 1

Then for every earlier index j < i, if:

nums[j] < nums[i]

we can append nums[i] after a subsequence ending at j.

Dynamic Programming Transition

For each pair j < i where nums[j] < nums[i], the candidate length is:

length[j] + 1

There are two cases.

If this candidate is longer than the current best ending at i, replace the best:

length[i] = length[j] + 1
count[i] = count[j]

If this candidate has the same length as the current best, add the number of ways:

count[i] += count[j]

This works because each valid subsequence ending at j can be extended by nums[i].

Algorithm

1. Let n = len(nums).
2. Create:
   • length = [1] * n
   • count = [1] * n
3. For each index i:
   • Look at every previous index j.
   • If nums[j] < nums[i], try to extend subsequences ending at j.
4. After filling the arrays:
   • Find max_length = max(length).
   • Sum count[i] for every index where length[i] == max_length.
5. Return that sum.

Correctness

For each index i, length[i] records the length of the longest strictly increasing subsequence that ends at nums[i].

The initialization is correct because every element alone forms an increasing subsequence of length 1.

When nums[j] < nums[i], every increasing subsequence ending at j can be extended by nums[i]. This gives subsequences ending at i with length length[j] + 1.

If this length is greater than the current length[i], the algorithm replaces the previous best and copies count[j], because all previous shorter endings at i are no longer longest for index i.

If this length equals the current length[i], the algorithm adds count[j], because it has found additional distinct subsequences ending at i with the same best length.

The algorithm considers every earlier valid predecessor j, so after processing all pairs, each length[i] and count[i] is correct.

Every longest increasing subsequence in the full array ends at some index i where length[i] equals the global maximum length. Summing count[i] over those indices counts all longest increasing subsequences exactly once.

Therefore, the algorithm returns the correct number.

Complexity

Implementation

from typing import List

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        length = [1] * n
        count = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] >= nums[i]:
                    continue

                candidate = length[j] + 1

                if candidate > length[i]:
                    length[i] = candidate
                    count[i] = count[j]
                elif candidate == length[i]:
                    count[i] += count[j]

        max_length = max(length)

        answer = 0

        for i in range(n):
            if length[i] == max_length:
                answer += count[i]

        return answer

Code Explanation

We initialize every element as a subsequence of length 1:

length = [1] * n
count = [1] * n

Then we process each index:

for i in range(n):

For every earlier index:

for j in range(i):

we check whether nums[j] can come before nums[i]:

if nums[j] >= nums[i]:
    continue

The strict inequality matters. Equal values cannot be part of the same increasing subsequence.

If the pair is valid, the new length is:

candidate = length[j] + 1

If this gives a longer subsequence ending at i, we replace the current best:

if candidate > length[i]:
    length[i] = candidate
    count[i] = count[j]

If it gives another way to reach the same best length, we add the count:

elif candidate == length[i]:
    count[i] += count[j]

After all DP states are computed, we find the global LIS length:

max_length = max(length)

Then sum the counts for every index that reaches that length:

for i in range(n):
    if length[i] == max_length:
        answer += count[i]

Testing

def run_tests():
    s = Solution()

    assert s.findNumberOfLIS([1, 3, 5, 4, 7]) == 2
    assert s.findNumberOfLIS([2, 2, 2, 2, 2]) == 5

    assert s.findNumberOfLIS([1, 2, 3, 4]) == 1
    assert s.findNumberOfLIS([4, 3, 2, 1]) == 4

    assert s.findNumberOfLIS([1, 2, 4, 3, 5, 4, 7, 2]) == 3
    assert s.findNumberOfLIS([1]) == 1

    print("all tests passed")

run_tests()

Test meaning: