LeetCode 673 - Number of Longest Increasing Subsequence

The problem asks us to determine how many longest strictly increasing subsequences exist in a given integer array. A subsequence is formed by deleting zero or more elements without changing the relative order of the remaining elements.

leetcodemediumarraydynamic-programmingbinary-indexed-treesegment-tree

LeetCode Problem 673

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Binary Indexed Tree, Segment Tree

Solution

Problem Understanding

The problem asks us to determine how many longest strictly increasing subsequences exist in a given integer array.

A subsequence is formed by deleting zero or more elements without changing the relative order of the remaining elements. For example, from [1,3,5,4,7], the subsequence [1,3,4,7] is valid because the order is preserved.

An increasing subsequence means every next element must be strictly larger than the previous one. Equal values are not allowed in the sequence.

The goal is not only to find the length of the longest increasing subsequence, commonly called LIS, but also to count how many different subsequences achieve that maximum length.

For example:

  • In [1,3,5,4,7], the LIS length is 4

  • There are two such subsequences:

  • [1,3,5,7]

  • [1,3,4,7]

  • Therefore, the answer is 2

The input constraints are important:

  • 1 <= nums.length <= 2000
  • Values can range from -10^6 to 10^6

An array size of 2000 is relatively moderate. This means an O(n^2) dynamic programming solution is acceptable because 2000^2 = 4,000,000, which is manageable. However, exponential solutions are completely infeasible.

Several edge cases are especially important:

  • Arrays where all elements are equal, such as [2,2,2,2]

  • Every single element forms an LIS of length 1

  • The answer becomes the number of elements

  • Strictly increasing arrays

  • Only one LIS exists

  • Strictly decreasing arrays

  • Every element individually forms an LIS of length 1

  • Duplicate values mixed with increasing values

  • Care must be taken not to incorrectly count equal values as increasing

The problem guarantees the final answer fits within a 32-bit integer, so we do not need special large integer handling.

Approaches

Brute Force Approach

The brute force solution generates every possible subsequence of the array and checks whether it is strictly increasing.

For each subsequence:

  1. Verify whether the subsequence is strictly increasing
  2. Track the maximum subsequence length seen so far
  3. Count how many subsequences achieve that length

This approach is correct because it explicitly evaluates every valid subsequence. However, an array of length n has 2^n possible subsequences, making this approach exponentially expensive.

For n = 2000, such a solution is impossible to run within time limits.

Key Insight for the Optimal Solution

The important observation is that every increasing subsequence ending at index i must come from some earlier index j where:

j < i and nums[j] < nums[i]

This naturally suggests dynamic programming.

For each position i, we want to know:

  • length[i]

  • The length of the longest increasing subsequence ending at i

  • count[i]

  • The number of LIS sequences ending at i

While iterating through previous indices:

  • If extending from j creates a longer subsequence than previously known for i, we update both length and count
  • If extending from j creates another subsequence with the same optimal length, we add its count

This allows us to compute the answer in O(n^2) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generates every subsequence and validates it
Optimal Dynamic Programming O(n^2) O(n) Tracks LIS length and count ending at each index

Algorithm Walkthrough

Step 1: Initialize DP Arrays

We create two arrays:

  • lengths[i]

  • Length of the LIS ending at index i

  • counts[i]

  • Number of LIS sequences ending at index i

Initially:

  • Every element alone forms a subsequence of length 1
  • There is exactly one such subsequence

So:

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

Step 2: Iterate Through Each Position

For every index i, we examine all earlier indices j.

for i in range(n):
    for j in range(i):

We only care about positions where:

nums[j] < nums[i]

because the subsequence must remain strictly increasing.

Step 3: Check Whether We Found a Better LIS

If extending the subsequence ending at j gives a longer subsequence for i:

lengths[j] + 1 > lengths[i]

then:

  • We found a better LIS ending at i
  • Replace the current best length
  • Copy the number of ways from j
lengths[i] = lengths[j] + 1
counts[i] = counts[j]

Step 4: Handle Equal-Length Alternatives

If extending from j gives another subsequence with the same best length:

lengths[j] + 1 == lengths[i]

then we add the counts:

counts[i] += counts[j]

This works because we discovered another distinct way to build an LIS ending at i.

Step 5: Find the Global LIS Length

After processing all indices:

max_length = max(lengths)

Step 6: Sum Counts for All Maximum-Length Subsequences

We sum all counts whose LIS length equals the global maximum.

answer = sum(counts[i] for i in range(n) if lengths[i] == max_length)

Why it works

The algorithm maintains the invariant that after processing index i, lengths[i] stores the longest increasing subsequence ending at i, and counts[i] stores exactly how many such optimal subsequences exist.

Every increasing subsequence ending at i must come from some earlier valid position j where nums[j] < nums[i]. By considering all such j, we guarantee that every possible LIS ending at i is accounted for. The update rules ensure we preserve only optimal lengths while correctly accumulating counts for equally optimal constructions.

Python Solution

from typing import List

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

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

        for i in range(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]

        longest_length = max(lengths)

        total = 0

        for i in range(n):
            if lengths[i] == longest_length:
                total += counts[i]

        return total

The implementation closely follows the dynamic programming strategy described earlier.

The lengths array tracks the longest increasing subsequence ending at each position. The counts array tracks how many optimal subsequences end there.

For every pair (j, i) where j < i, we attempt to extend the subsequence ending at j using nums[i].

When we discover a strictly better subsequence length, we overwrite both the length and count. When we discover another subsequence with the same optimal length, we accumulate the counts.

At the end, the global LIS length is computed, and we sum all counts associated with that maximum length.

Go Solution

func findNumberOfLIS(nums []int) int {
	n := len(nums)

	lengths := make([]int, n)
	counts := make([]int, n)

	for i := 0; i < n; i++ {
		lengths[i] = 1
		counts[i] = 1
	}

	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				if lengths[j]+1 > lengths[i] {
					lengths[i] = lengths[j] + 1
					counts[i] = counts[j]
				} else if lengths[j]+1 == lengths[i] {
					counts[i] += counts[j]
				}
			}
		}
	}

	longestLength := 0

	for _, length := range lengths {
		if length > longestLength {
			longestLength = length
		}
	}

	total := 0

	for i := 0; i < n; i++ {
		if lengths[i] == longestLength {
			total += counts[i]
		}
	}

	return total
}

The Go implementation is nearly identical to the Python version in logic and structure.

Slices are used instead of Python lists. Since Go arrays are initialized with zero values, we explicitly set every position in lengths and counts to 1.

Go uses standard integer arithmetic, and the problem guarantees the answer fits within a 32-bit integer, so overflow is not a concern here.

Worked Examples

Example 1

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

Initial state:

Index Value lengths counts
0 1 1 1
1 3 1 1
2 5 1 1
3 4 1 1
4 7 1 1

Process index 1 (3):

  • 1 < 3
  • Extend subsequence
Index lengths counts
1 2 1

Current arrays:

lengths = [1,2,1,1,1]
counts  = [1,1,1,1,1]

Process index 2 (5):

From 1:

  • length becomes 2

From 3:

  • length becomes 3
lengths = [1,2,3,1,1]
counts  = [1,1,1,1,1]

Process index 3 (4):

From 1:

  • length becomes 2

From 3:

  • length becomes 3

5 cannot extend because 5 > 4

lengths = [1,2,3,3,1]
counts  = [1,1,1,1,1]

Process index 4 (7):

From 1:

  • candidate length 2

From 3:

  • candidate length 3

From 5:

  • candidate length 4
  • count becomes 1

From 4:

  • another candidate length 4
  • add another count
lengths = [1,2,3,3,4]
counts  = [1,1,1,1,2]

Maximum LIS length is 4.

Total count is 2.

Answer:

2

Example 2

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

No element can extend another because the sequence must be strictly increasing.

Final arrays:

lengths = [1,1,1,1,1]
counts  = [1,1,1,1,1]

Maximum length:

1

Total count:

1 + 1 + 1 + 1 + 1 = 5

Answer:

5

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Every pair of indices (j, i) is examined once
Space O(n) Two DP arrays of size n are maintained

The nested loops dominate the runtime. For each index i, we examine all earlier indices j, leading to quadratic complexity.

The memory usage remains linear because only two arrays proportional to the input size are stored.

Test Cases

from typing import List

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

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

        for i in range(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]

        longest_length = max(lengths)

        return sum(
            counts[i]
            for i in range(n)
            if lengths[i] == longest_length
        )

solution = Solution()

assert solution.findNumberOfLIS([1,3,5,4,7]) == 2  # Multiple LIS paths
assert solution.findNumberOfLIS([2,2,2,2,2]) == 5  # All equal elements
assert solution.findNumberOfLIS([1]) == 1  # Single element
assert solution.findNumberOfLIS([1,2,3,4,5]) == 1  # Strictly increasing
assert solution.findNumberOfLIS([5,4,3,2,1]) == 5  # Strictly decreasing
assert solution.findNumberOfLIS([1,2,4,3,5,4,7,2]) == 3  # Multiple branching LIS
assert solution.findNumberOfLIS([1,3,2]) == 2  # Two LIS of length 2
assert solution.findNumberOfLIS([1,1,1,2,2,2]) == 9  # Duplicate combinations
assert solution.findNumberOfLIS([-1,-2,-3,-4]) == 4  # Negative decreasing
assert solution.findNumberOfLIS([1,5,2,6,3,7]) == 1  # Unique LIS
Test Why
[1,3,5,4,7] Standard example with multiple LIS
[2,2,2,2,2] Ensures strict inequality handling
[1] Minimum input size
[1,2,3,4,5] Single increasing path
[5,4,3,2,1] Every element forms LIS length 1
[1,2,4,3,5,4,7,2] Complex branching subsequences
[1,3,2] Multiple LIS with short length
[1,1,1,2,2,2] Duplicate value combinations
[-1,-2,-3,-4] Negative decreasing sequence
[1,5,2,6,3,7] Verifies unique maximum sequence

Edge Cases

One important edge case occurs when all elements are identical, such as [2,2,2,2]. Since the problem requires strictly increasing subsequences, equal values cannot extend each other. A buggy implementation might incorrectly treat equal values as valid extensions. This solution explicitly checks nums[j] < nums[i], preventing that mistake. Every element independently contributes a subsequence of length 1.

Another critical edge case is a strictly decreasing array like [5,4,3,2,1]. In this scenario, no increasing subsequence longer than 1 exists. The correct answer is the number of elements because each individual value forms its own LIS. The initialization of lengths and counts to 1 guarantees this case is handled naturally without special logic.

A more subtle edge case involves duplicate values mixed with increasing subsequences, such as [1,1,1,2,2,2]. Multiple different index combinations produce valid LIS sequences. The counting logic must correctly accumulate counts from multiple predecessors without overwriting them incorrectly. The elif lengths[j] + 1 == lengths[i] branch ensures all equally optimal paths are counted.

Another important case is a single-element array. The longest increasing subsequence has length 1, and exactly one such subsequence exists. Since the DP arrays are initialized with 1, the implementation immediately produces the correct answer.