Skip to main content

673. Number of Longest Increasing Subsequence

medium

Count how many strictly-increasing subsequences achieve the maximum length. The LIS pattern with a parallel count array tracking ties.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing.

Constraints

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6

Examples

Example 1

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

Explanation: 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

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Run the O(n^2) LIS DP but keep a parallel count[i] = number of LIS ending at i.

Hint 2

When dp[j] + 1 > dp[i] set dp[i] = dp[j] + 1 and count[i] = count[j]. On equal, add: count[i] += count[j].

Hint 3

Sum count[i] over all i where dp[i] equals the global max length.

Solution approach

Reveal approach

Two parallel 1D arrays. dp[i] = length of the longest strictly-increasing subsequence ending at index i. count[i] = the number of such longest subsequences ending at i. Initialize dp[i] = 1 and count[i] = 1. For i from 0 to n-1 and j from 0 to i-1: if nums[j] < nums[i], compare dp[j] + 1 to dp[i]. If strictly greater, set dp[i] = dp[j] + 1 and count[i] = count[j] (replace). If equal, count[i] += count[j] (merge). Find max_len = max(dp). Return sum of count[i] over indices where dp[i] == max_len. O(n^2) time, O(n) space.

Complexity

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

Related patterns

  • dynamic-programming
  • lis

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Number of Longest Increasing Subsequence and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →