We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Longest Increasing Subsequence

Number: 673

Difficulty: Medium

Paid? No

Companies: TikTok, Intuit, Commvault, Meta

Problem Description

Given an integer array nums, return the number of longest strictly increasing subsequences in the array. Note that the subsequence does not have to be contiguous.

Key Insights

  • Use dynamic programming to keep track of both the length of the longest increasing subsequence (LIS) ending at each index and the number of ways to achieve that length.
  • Maintain two arrays: one (dp) for the length of the LIS ending at the current index, and another (count) for the number of such LIS ending at that index.
  • For each element, iterate over all previous elements; if a previous element is less than the current one, update the dp and count arrays.
  • After processing, the result is the sum of counts for indices where the dp value equals the maximum length found.

Space and Time Complexity

Time Complexity: O(n²)
Space Complexity: O(n)

Solution

The solution uses dynamic programming with two auxiliary arrays. The dp array stores the length of the longest increasing subsequence ending at each index. The count array stores the number of ways to achieve that length at each index.

For every index i, loop through all previous indices j. If nums[j] is less than nums[i], meaning an increasing sequence can be formed:

  • If extending the sequence from j gives a longer subsequence than previously recorded for i (i.e., dp[j] + 1 > dp[i]), update dp[i] and set count[i] equal to count[j].
  • If it equals the already found length (i.e., dp[j] + 1 == dp[i]), then add count[j] to count[i] because another sequence of the same length is found.

Finally, the answer is computed by summing all count[i] for which dp[i] equals the maximum value in dp.

Code Solutions

# Python solution for Number of Longest Increasing Subsequence

def findNumberOfLIS(nums):
    # Get the length of the input array
    n = len(nums)
    
    # If the list is empty, return 0 (edge-case)
    if n == 0:
        return 0
    
    # dp[i] stores the length of the longest increasing subsequence ending at i
    dp = [1] * n
    # count[i] stores the number of longest increasing subsequences ending at i
    count = [1] * n
    
    # Iterate over each element in nums
    for i in range(n):
        # Check all previous elements to update dp[i] and count[i]
        for j in range(i):
            if nums[j] < nums[i]:
                # Found a potential sequence ending at i
                if dp[j] + 1 > dp[i]:
                    # A longer subsequence is found, update length and count
                    dp[i] = dp[j] + 1
                    count[i] = count[j]
                elif dp[j] + 1 == dp[i]:
                    # Found another subsequence of the same maximum length ending at i, add count
                    count[i] += count[j]
    
    # Find the length of the overall longest increasing subsequence in the array
    longest = max(dp)
    # Sum the number of ways for all indices that achieve this longest length
    ans = sum(c for i, c in enumerate(count) if dp[i] == longest)
    
    return ans

# Example usage
# nums = [1,3,5,4,7]
# print(findNumberOfLIS(nums))  # Output should be 2
← Back to All Questions