Domain 2MediumMEDIUM

Number of Longest Increasing Subsequence

LeetCode problem 673: Number of Longest Increasing Subsequence (medium).

Domain: medium•Updated: 2026-08-30
#Dynamic Programming

Problem Breakdown

We are given an array of integers and need to find how many distinct subsequences exist that have the maximum possible length among all strictly increasing ones.

Key Inputs: An integer list nums.
Output: A single integer representing the count of Longest Increasing Subsequences (LIS).

Constraints & Edge Cases:

  1. Strictly Increasing: [1, 3] is valid; [1, 1] is not. This means we cannot extend a subsequence if nums[j] >= nums[i].
  2. Duplicates: If the input is all identical (e.g., [2, 2, 2]), every single element forms an LIS of length 1. The answer should be NN, not just one count.
  3. Lengths: nums.length <= 2000. This suggests an O(N2)O(N^2) solution is acceptable (4×1064 \times 10^6 ops), whereas exponential solutions are impossible.

Intuition

A brute-force approach would generate all possible subsequences, check if they are increasing, calculate their lengths, and count the maximums. That takes O(3N/2)O(3^{N/2}), which is too slow for N=2000N=2000.

We need Dynamic Programming (DP). For each element nums[i], we want to know two things:

  1. What is the length of the longest increasing subsequence ending at index i? Let’s call this len[i].
  2. How many such subsequences exist with that specific length ending at i? Let’s call this count[i].

When we process a new element nums[i], we look back at all previous elements nums[j] (where j<ij < i).

  • If nums[j] < nums[i]: We can extend the subsequence ending at j.
    • Case 1: Extending it makes a longer sequence than what we’ve seen for i so far (len[j] + 1 > len[i]). We update len[i] and reset count[i] to match count[j].
    • Case 2: Extending it matches the current best length found at i (len[j] + 1 == len[i]). This means we’ve found another way to form a subsequence of this max length ending here. We add count[j] to count[i].

Finally, after filling our DP tables for all indices, the answer is the sum of count[i] for every index where len[i] equals the global maximum LIS length found in the array.

Approach

  1. Initialize two arrays: lengths and counts, both size NN, filled with 1 (since each element itself is a subsequence of length 1).
  2. Iterate through every index i from 0 to n-1.
  3. Inside, iterate backwards or forwards through all previous indices j < i.
  4. Apply the transition logic: if nums[j] < nums[i]:
    • If lengths[j] + 1 > lengths[i], update lengths[i] and set counts[i] = counts[j].
    • Else if lengths[j] + 1 == lengths[i], add counts[j] to counts[i].
  5. Track the global maximum length (max_len) encountered during iteration or find it after filling arrays.
  6. Sum up all values in counts where the corresponding value in lengths equals max_len.

Complexity Analysis

  • Time: O(N2)O(N^2). We have nested loops iterating over pairs of indices (i,j)(i, j) with j<ij < i. Given constraints (N≤2000N \le 2000), this fits within typical time limits for Python.
  • Space: O(N)O(N). We store two arrays (lengths and counts) proportional to the input size.

Solution

class Solution:
    def findNumberOfLIS(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        
        # lengths[i] stores the length of LIS ending at index i
        # counts[i] stores the number of such subsequences ending at index i
        lengths = [1] * n
        counts = [1] * n
        
        max_len = 0

        for i in range(n):
            current_max_len_at_i = 0
            
            for j in range(i):
                if nums[j] < nums[i]:
                    # If we can extend a longer subsequence found at j
                    if lengths[j] + 1 > lengths[i]:
                        lengths[i] = lengths[j] + 1
                        counts[i] = counts[j]
                    elif lengths[j] + 1 == lengths[i]:
                        # Found another way to achieve the same max length ending here
                        counts[i] += counts[j]
            
            if lengths[i] > max_len:
                max_len = lengths[i]

        total_count = 0
        for i in range(n):
            if lengths[i] == max_len:
                total_count += counts[i]
                
        return total_count

Edge Cases Handled

  • All Duplicates: The logic ensures lengths stays at 1, and since every element is valid (strictly increasing condition fails for duplicates), the code correctly sums all NN elements as they each form a length-1 LIS.
  • Strictly Increasing Array: Only one path exists to build the sequence; counts propagate exactly once per level, resulting in total_count = 1.
  • Decreasing Array: No element can extend another (nums[j] < nums[i] never true). All lengths remain 1. Max length is 1. Sum of counts for all indices equals NN.