LeetCode 673: Number of Longest Increasing Subsequence Solution in Python – A Step-by-Step Guide

Imagine you’re a sequence hunter exploring an array like [1, 3, 5, 4, 7], and your mission is to count how many longest increasing subsequences exist—sequences where numbers rise step-by-step, like [1, 3, 5, 7] and [1, 3, 4, 7], both of length 4, totaling 2. That’s the challenge of LeetCode 673: Number of Longest Increasing Subsequence, a medium-level problem that’s all about tracking both the length and count of increasing subsequences in an array. Using Python, we’ll explore two solutions: the Best Solution, a dynamic programming approach with length and count arrays for efficiency, and an Alternative Solution, a brute-force method with subsequence generation that’s simpler but slower. With detailed examples, beginner-friendly breakdowns—especially for the DP method—and clear code, this guide will help you count those subsequences, whether you’re new to coding or leveling up. Let’s dive into that array and start hunting!

What Is LeetCode 673: Number of Longest Increasing Subsequence?

In LeetCode 673: Number of Longest Increasing Subsequence, you’re given an integer array nums, and your task is to find the number of longest increasing subsequences (LIS) within it. An increasing subsequence is a sequence of numbers where each element is strictly greater than the previous one, and you need to count how many such subsequences achieve the maximum possible length. Return this count as an integer. For example, with nums = [1, 3, 5, 4, 7], the longest increasing subsequences are [1, 3, 5, 7] and [1, 3, 4, 7], both of length 4, so the answer is 2. This problem tests your ability to extend the classic LIS problem by counting occurrences rather than just finding the length.

Problem Statement

Input:

nums: List of integers.

Output: An integer—number of longest increasing subsequences.
Rules:

Increasing subsequence: Each element > previous.
Find maximum length of such subsequences.
Count how many achieve this length.

Constraints

1 ≤ nums.length ≤ 2000.
-10⁶ ≤ nums[i] ≤ 10⁶.

Examples

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

Output: 2 (LIS: [1, 3, 5, 7], [1, 3, 4, 7])

Input: nums = [2, 2, 2, 2, 2]

Output: 5 (LIS: [2] five times, length 1)

Input: nums = [1, 2, 4, 3, 5, 4, 7, 2]

Output: 3 (LIS: [1, 2, 4, 5, 7], [1, 2, 4, 4, 7], [1, 2, 3, 5, 7])

These examples set the array—let’s solve it!

Understanding the Problem: Counting Longest Subsequences

To solve LeetCode 673: Number of Longest Increasing Subsequence in Python, we need to determine the length of the longest increasing subsequence (LIS) in nums and count how many subsequences achieve that length. A brute-force approach—generating all subsequences and filtering—would be O(2^n), impractical for n ≤ 2000. Since LIS is a classic DP problem, we can extend it to track counts efficiently. We’ll use:

Best Solution (Dynamic Programming with Length and Count Arrays): O(n²) time, O(n) space—fast and optimal.
Alternative Solution (Brute-Force with Subsequence Generation): O(2^n) time, O(2^n) space—simple but slow.

Let’s start with the DP solution, breaking it down for beginners.

Best Solution: Dynamic Programming with Length and Count Arrays

Why This Is the Best Solution

The dynamic programming with length and count arrays approach is the top choice for LeetCode 673 because it’s efficient—O(n²) time with O(n) space—and builds on the classic LIS solution by maintaining two arrays: one for the length of the longest increasing subsequence ending at each index, and another for the count of such subsequences. It fits constraints (n ≤ 2000) perfectly and is clear once you see the DP logic. It’s like building a map of lengths and counts to tally the winners!

How It Works

Think of this as a sequence counter:

Step 1: Initialize Arrays:

length[i]: Length of LIS ending at nums[i].
count[i]: Number of LIS ending at nums[i].
Base: length[i] = 1, count[i] = 1 (single element).

Step 2: Fill DP Arrays:

For each i from 0 to n-1:

For j from 0 to i-1:

If nums[j] < nums[i]:

If length[j] + 1 > length[i]: Update length[i], count[i] = count[j].
If length[j] + 1 = length[i]: Add count[j] to count[i].

Step 3: Find Max Length and Count:

Scan length for max_length.
Sum count[i] where length[i] = max_length.

Step 4: Return Result:

Return total count.

It’s like a length-and-count tracker—build and tally!

Step-by-Step Example

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

Step 1: Init:

length = [1, 1, 1, 1, 1].
count = [1, 1, 1, 1, 1].

Step 2: Fill DP:

i=0 (1): Base.
i=1 (3): j=0 (1<3), length[1] = 2, count[1] = 1.
i=2 (5): j=0 (1<5), length[2] = 2, count[2] = 1; j=1 (3<5), length[2] = 3, count[2] = 1.
i=3 (4): j=0 (1<4), length[3] = 2, count[3] = 1; j=1 (3<4), length[3] = 2, count[3] = 1+1=2.
i=4 (7): j=0 (1<7), length[4] = 2, count[4] = 1; j=1 (3<7), length[4] = 3, count[4] = 1; j=2 (5<7), length[4] = 4, count[4] = 1; j=3 (4<7), length[4] = 3, count[4] = 2.
Final: length = [1, 2, 3, 2, 4], count = [1, 1, 1, 2, 1].

Step 3: Max_length = 4, count where length=4: count[4] = 1 + count[3] = 2 (from [1,3,5,7] and [1,3,4,7]).
Step 4: Return 2.
Output: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # Step 1: Initialize arrays
        n = len(nums)
        length = [1] * n  # Length of LIS ending at i
        count = [1] * n   # Count of LIS ending at i

        # Step 2: Fill DP arrays
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        count[i] = count[j]
                    elif length[j] + 1 == length[i]:
                        count[i] += count[j]

        # Step 3: Find max length and total count
        max_length = max(length)
        total_count = sum(c for l, c in zip(length, count) if l == max_length)

        # Step 4: Return result
        return total_count

Lines 4-7: Init: Arrays for length and count, all 1s.
Lines 10-16: Fill:

Compare each pair, update length and count based on LIS rules.

Lines 19-20: Find:

Max length, sum counts where length matches max.

Line 23: Return total_count.
Time Complexity: O(n²)—nested loops over n elements.
Space Complexity: O(n)—two arrays.

This is like a sequence tallier—track and count!

Alternative Solution: Brute-Force with Subsequence Generation

Why an Alternative Approach?

The brute-force with subsequence generation approach enumerates all increasing subsequences—O(2^n) time, O(2^n) space. It’s simpler conceptually, generating all possibilities and counting the longest, but inefficient for larger n. It’s like listing every path and picking the winners!

How It Works

Picture this as a subsequence lister:

Step 1: Generate all increasing subsequences:

Use recursion or iteration to build sequences.

Step 2: Track lengths and counts:

Store in a list or dict.

Step 3: Find max length and count:

Filter for longest, count occurrences.

Step 4: Return count.

It’s like a list maker—generate and tally!

Step-by-Step Example

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

Step 1: Generate:

[1], [3], [5], [4], [7].
[1,3], [1,5], [1,4], [1,7], [3,5], [3,4], [3,7], [5,7], [4,7].
[1,3,5], [1,3,4], [1,3,7], [1,4,7], [1,5,7], [3,5,7], [3,4,7].
[1,3,5,7], [1,3,4,7].

Step 2: Lengths: 1 (5), 2 (9), 3 (7), 4 (2).
Step 3: Max length = 4, count = 2.
Step 4: Return 2.
Output: 2.

Code for Brute-Force Approach

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # Step 1: Generate all increasing subsequences
        def generate_subsequences(index, curr_seq):
            if index == len(nums):
                if curr_seq:
                    seqs.append(curr_seq[:])
                return
            # Include current
            if not curr_seq or nums[index] > curr_seq[-1]:
                curr_seq.append(nums[index])
                generate_subsequences(index + 1, curr_seq)
                curr_seq.pop()
            # Exclude current
            generate_subsequences(index + 1, curr_seq)

        seqs = []
        generate_subsequences(0, [])

        # Step 2: Find max length and count
        if not seqs:
            return 0
        max_length = max(len(seq) for seq in seqs)
        count = sum(1 for seq in seqs if len(seq) == max_length)

        # Step 3: Return result
        return count

Lines 4-15: Generate:

Recursively build increasing subsequences.

Lines 18-23: Find:

Max length, count sequences matching it.

Line 26: Return count.
Time Complexity: O(2^n)—exponential subsequence generation.
Space Complexity: O(2^n)—store all subsequences.

It’s a sequence generator—list and count!

Comparing the Two Solutions

DP (Best):

Pros: O(n²) time, O(n) space, efficient and scalable.
Cons: DP logic less obvious.

Brute-Force (Alternative):

Pros: O(2^n) time, O(2^n) space, straightforward.
Cons: Inefficient for large n.

DP wins for efficiency.

Additional Examples and Edge Cases

Input: [1]

Output: 1.

Input: [1, 2]

Output: 1 (Only [1, 2]).

DP handles these well.

Complexity Breakdown

DP: Time O(n²), Space O(n).
Brute-Force: Time O(2^n), Space O(2^n).

DP is optimal.

Key Takeaways

DP: Length and count—smart!
Brute-Force: Subsequence listing—clear!
LIS: Counting is fun.
Python Tip: DP rocks—see Python Basics.

Final Thoughts: Count Those Subsequences

LeetCode 673: Number of Longest Increasing Subsequence in Python is a fun sequence challenge. DP with length and count arrays offers speed and precision, while brute-force provides a clear baseline. Want more? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 1143: Longest Common Subsequence. Ready to hunt? Head to Solve LeetCode 673 on LeetCode and count those LIS today!