Scale Engineer

Number of Longest Increasing Subsequence

Med
#0627Time: O(N^2), where N is the length of `nums`. The nested loops to compare each element with all its predecessors result in a quadratic runtime.Space: O(N), where N is the length of `nums`. We use two arrays, `length` and `count`, of size N.2 companies
Patterns
Dynamic Programming
Data structures
ArrayBinary Indexed TreeSegment Tree
Companies
IntuitCommvault

Prompt

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

 

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.

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. It maintains two arrays: one to track the length of the longest increasing subsequence (LIS) ending at each position, and another to track the count of such subsequences. By iterating through the array and comparing each element with all previous elements, it builds up the lengths and counts for all possible LIS.

Algorithm

  • Initialize two arrays, length and count, of size n (the length of nums), and fill them with 1.
  • length[i] will store the length of the longest increasing subsequence (LIS) ending at index i.
  • count[i] will store the number of such LIS ending at index i.
  • Iterate through the nums array with an outer loop from i = 0 to n-1.
  • Inside, have a nested loop from j = 0 to i-1.
  • If nums[i] > nums[j], we can extend the subsequence ending at j.
    • If length[j] + 1 > length[i], we have found a new, longer LIS ending at i. Update length[i] = length[j] + 1 and reset count[i] = count[j].
    • If length[j] + 1 == length[i], we have found another way to form an LIS of the same length. We add the counts: count[i] += count[j].
  • After the loops, find the maximum length (maxLength) in the length array.
  • Iterate through the length array one last time. Sum up all count[i] where length[i] is equal to maxLength.
  • Return the final sum.

Walkthrough

In this method, we use two arrays, length and count, both of size n, where n is the length of the input array nums.

  • length[i]: Stores the length of the longest increasing subsequence that ends with the element nums[i].
  • count[i]: Stores the number of distinct longest increasing subsequences that end with the element nums[i].

We initialize length[i] and count[i] to 1 for all i, as any single element itself is an increasing subsequence of length 1.

We then iterate from the first element to the last. For each element nums[i], we iterate through all previous elements nums[j] (where j < i). If nums[i] is strictly greater than nums[j], it means we can extend an increasing subsequence ending at j.

There are two cases:

  1. If extending the subsequence at j gives a longer subsequence for i (i.e., length[j] + 1 > length[i]), we've found a new maximum length for LIS ending at i. We update length[i] to this new length and set count[i] to be count[j], because all the ways to form the LIS ending at j now extend to a new LIS ending at i.
  2. If extending the subsequence at j results in a subsequence of the same length as the current LIS for i (i.e., length[j] + 1 == length[i]), it means we've found an alternative way to form the LIS of that length. So, we add count[j] to count[i].

After populating both arrays, we find the overall maxLength of any LIS by finding the maximum value in the length array. Finally, we sum up the count[i] for all indices i where length[i] equals maxLength to get the total number of longest increasing subsequences.

import java.util.Arrays; class Solution {    public int findNumberOfLIS(int[] nums) {        int n = nums.length;        if (n <= 1) {            return n;        }        // length[i] = length of LIS ending at nums[i]        int[] length = new int[n];         // count[i] = number of LIS ending at nums[i]        int[] count = new int[n];          Arrays.fill(length, 1);        Arrays.fill(count, 1);         for (int i = 0; i < n; i++) {            for (int j = 0; j < i; j++) {                if (nums[i] > nums[j]) {                    if (length[j] + 1 > length[i]) {                        length[i] = length[j] + 1;                        count[i] = count[j]; // Reset count                    } else if (length[j] + 1 == length[i]) {                        count[i] += count[j]; // Add ways                    }                }            }        }         int maxLength = 0;        for (int len : length) {            maxLength = Math.max(maxLength, len);        }         int result = 0;        for (int i = 0; i < n; i++) {            if (length[i] == maxLength) {                result += count[i];            }        }        return result;    }}

Complexity

Time

O(N^2), where N is the length of `nums`. The nested loops to compare each element with all its predecessors result in a quadratic runtime.

Space

O(N), where N is the length of `nums`. We use two arrays, `length` and `count`, of size N.

Trade-offs

Pros

  • It is relatively straightforward to understand and implement.

  • The logic directly follows the definition of the problem.

Cons

  • The O(N^2) time complexity makes it slow for large input arrays, potentially leading to a 'Time Limit Exceeded' error on competitive programming platforms.

Solutions

class BinaryIndexedTree { private int n ; private int [] c ; private int [] d ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; d = new int [ n + 1 ]; } public void update ( int x , int v , int cnt ) { while ( x <= n ) { if ( c [ x ] < v ) { c [ x ] = v ; d [ x ] = cnt ; } else if ( c [ x ] == v ) { d [ x ] += cnt ; } x += x & - x ; } } public int [] query ( int x ) { int v = 0 , cnt = 0 ; while ( x > 0 ) { if ( c [ x ] > v ) { v = c [ x ]; cnt = d [ x ]; } else if ( c [ x ] == v ) { cnt += d [ x ]; } x -= x & - x ; } return new int [] { v , cnt }; } } public class Solution { public int findNumberOfLIS ( int [] nums ) { // int[] arr = Arrays.stream(nums).distinct().sorted().toArray(); int [] arr = nums . clone (); Arrays . sort ( arr ); int m = arr . length ; BinaryIndexedTree tree = new BinaryIndexedTree ( m ); for ( int x : nums ) { int i = Arrays . binarySearch ( arr , x ) + 1 ; int [] t = tree . query ( i - 1 ); int v = t [ 0 ]; int cnt = t [ 1 ]; tree . update ( i , v + 1 , Math . max ( cnt , 1 )); } return tree . query ( m )[ 1 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem