#673

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Longest Increasing Subsequence

This problem challenges you to find the number of longest increasing subsequences in a given array of integers.

array dynamic programming binary indexed tree segment tree

Problem Statement

You are given an integer array nums. Your task is to return the number of longest increasing subsequences (LIS) that can be formed from the array. A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements. The subsequence must be strictly increasing, meaning each element must be greater than the previous one.

For example, in the array nums = [1,3,5,4,7], there are two longest increasing subsequences: [1, 3, 4, 7] and [1, 3, 5, 7]. You are required to compute the count of these subsequences.

Examples

Example 1

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

Output: 2

The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2

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

Output: 5

The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

Constraints

1 <= nums.length <= 2000
-106 <= nums[i] <= 106
The answer is guaranteed to fit inside a 32-bit integer.

Solution Approach

State Transition Dynamic Programming

We approach this problem by iterating through the array and maintaining a dynamic programming (DP) array where dp[i] represents the length of the longest increasing subsequence that ends at the element nums[i]. A second array, count[i], tracks the number of ways to form the LIS ending at nums[i]. By iterating through each pair of indices, we update both dp and count values to reflect the longest subsequences and their frequency.

Time and Space Optimization

The time complexity of a brute force solution would be O(n^2), as for each element we compare it with all previous ones. However, the use of dynamic programming optimizes this to O(n^2) for the time complexity. Space complexity can be reduced to O(n) since only two arrays (dp and count) are required.

Binary Indexed Tree (BIT) Approach (Advanced)

For more advanced optimizations, a Binary Indexed Tree (BIT) can be utilized to compute the LIS in logarithmic time for updates and queries. This would reduce the overall complexity when solving the problem for large inputs, making it feasible for the upper constraint limits.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n)

The time complexity of the solution is O(n^2) due to the nested iteration for comparison of elements in the array. Space complexity is O(n), as we only need arrays for storing the lengths and counts of the LIS at each index.

What Interviewers Usually Probe

Candidate should be comfortable explaining the state transition dynamic programming approach.
Look for understanding of optimization techniques, such as reducing space complexity or utilizing a BIT.
Assess the candidate's ability to handle larger inputs efficiently and discuss the trade-offs between time and space complexity.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update both dp and count arrays correctly during the iterations can lead to wrong counts.
Misunderstanding the problem constraints can lead to inefficient solutions that fail for larger inputs.
Not recognizing the need for optimization, especially in terms of space complexity when handling large datasets.

Follow-up variants

Find the number of longest increasing subsequences with additional constraints on elements.
Consider variations that involve non-strictly increasing subsequences or variations in element restrictions.
Handle cases with negative numbers and zeroes in the array, ensuring that these do not affect the LIS calculation.

FAQ

How do you approach the Number of Longest Increasing Subsequence problem?

The Number of Longest Increasing Subsequence problem is best solved using state transition dynamic programming. You maintain two arrays, dp and count, to track the length of subsequences and the number of ways to form them.

What is the time complexity of the solution?

The time complexity of this solution is O(n^2) because of the nested loops comparing each element with all previous elements to update the dp and count arrays.

How can you optimize the space complexity of this problem?

The space complexity can be optimized to O(n) by using only two arrays, dp and count, instead of storing the entire state of subsequences at each step.

What other optimizations can be applied to this problem?

You can apply a Binary Indexed Tree (BIT) to reduce the complexity of updates and queries, potentially improving the performance for large input sizes.

What is the significance of the count array in the solution?

The count array tracks how many different subsequences result in the same length of LIS at a given index. This ensures that we correctly count all possible LIS that end at each index.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ as the length of the longest increasing subsequence ending with $nums[i]$, and $cnt[i]$ as the number of longest increasing subsequences ending with $nums[i]$. Initially, $f[i]=1$, $cnt[i]=1$. Also, we define $mx$ as the length of the longest increasing subsequence, and $ans$ as the number of longest increasing subsequences.

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [1] * n
        cnt = [1] * n
        mx = 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if f[i] < f[j] + 1:
                        f[i] = f[j] + 1
                        cnt[i] = cnt[j]
                    elif f[i] == f[j] + 1:
                        cnt[i] += cnt[j]
            if mx < f[i]:
                mx = f[i]
                ans = cnt[i]
            elif mx == f[i]:
                ans += cnt[i]
        return ans

Solution 2: Binary Indexed Tree

We can use a binary indexed tree to maintain the length and count of the longest increasing subsequence in the prefix interval. We remove duplicates from the array $nums$ and sort it to get the array $arr$. Then we enumerate each element $x$ in $nums$, find the position $i$ of $x$ in the array $arr$ by binary search, then query the length and count of the longest increasing subsequence in $[1,i-1]$, denoted as $v$ and $cnt$, then update the length and count of the longest increasing subsequence in $[i]$ to $v+1$ and $\max(cnt,1)$. Finally, we query the length and count of the longest increasing subsequence in $[1,m]$, where $m$ is the length of the array $arr$, which is the answer.

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [1] * n
        cnt = [1] * n
        mx = 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if f[i] < f[j] + 1:
                        f[i] = f[j] + 1
                        cnt[i] = cnt[j]
                    elif f[i] == f[j] + 1:
                        cnt[i] += cnt[j]
            if mx < f[i]:
                mx = f[i]
                ans = cnt[i]
            elif mx == f[i]:
                ans += cnt[i]
        return ans

Continue Practicing

#1395 count number of teams #493 reverse pairs #406 queue reconstruction by height