Number of Longest Increasing Subsequence

Medium
314.

Number of Longest Increasing Subsequence

Number of Longest Increasing Subsequence is a medium coding problem on arrays, dynamic programming and binary indexed tree, asked in Amazon, Google and Meta interviews.

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

Example 1

Input
nums = [1,3,5,4,7]
Output
2
Explanation
The two longest are [1,3,4,7] and [1,3,5,7].

Example 2

Input
nums = [2,2,2,2,2]
Output
5
Explanation
The longest has length 1, and there are five of them.

Example 3

Input
nums = [1]
Output
1

Constraints

  • 1 <= nums.length <= 30
  • -1000 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Longest Increasing Subsequence — Solution

Number of Longest Increasing Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Longest Increasing Subsequence is a medium coding problem on arrays, dynamic programming and binary indexed tree, asked in Amazon, Google and Meta interviews.

Problem statement

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

Example 1

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest are [1,3,4,7] and [1,3,5,7].

Example 2

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The longest has length 1, and there are five of them.

Example 3

Input: nums = [1]
Output: 1

Constraints

  • 1 <= nums.length <= 30
  • -1000 <= nums[i] <= 1000

Hints for Number of Longest Increasing Subsequence

  1. Hint 1

    Extend the usual O(n²) LIS with a second table: how many longest chains end at each index.

  2. Hint 2

    When a longer chain is found, the count is replaced; when an equally long one is found, the counts add.

  3. Hint 3

    The answer sums the counts at every index whose chain length equals the global maximum.

How to solve Number of Longest Increasing Subsequence

Run the O(n²) LIS with a second table counting how many longest chains end at each index; a strictly longer chain replaces the count, an equal one adds to it.

Approach

  1. For each i and each j < i with nums[j] < nums[i]: if length[j] + 1 > length[i], set length[i] and count[i] = count[j]; if equal, count[i] += count[j].
  2. Sum count[i] over indices whose length[i] equals the global maximum.

Why it works

Every longest chain ending at i passes through some j with length[j] = length[i] - 1, and distinct j (or distinct chains through the same j) give distinct chains, so the counts add exactly.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • Use count[i] = count[j] on a strict improvement, not +=.

Reference solution

Python

def findNumberOfLIS(nums) -> int:
    n = len(nums)
    length = [1] * n
    count = [1] * n
    best = 1
    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]
        best = max(best, length[i])
    return sum(count[i] for i in range(n) if length[i] == best)

Java

public static int findNumberOfLIS(int[] nums) {
    int n = nums.length;
    int[] len = new int[n];
    int[] count = new int[n];
    Arrays.fill(len, 1);
    Arrays.fill(count, 1);
    int best = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    count[i] = count[j];
                } else if (len[j] + 1 == len[i]) {
                    count[i] += count[j];
                }
            }
        }
        if (len[i] > best) best = len[i];
    }
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (len[i] == best) total += count[i];
    }
    return total;
}

C++

int findNumberOfLIS(vector<int>& nums) {
    int n = (int) nums.size();
    vector<int> len(n, 1), count(n, 1);
    int best = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    count[i] = count[j];
                } else if (len[j] + 1 == len[i]) {
                    count[i] += count[j];
                }
            }
        }
        best = max(best, len[i]);
    }
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (len[i] == best) total += count[i];
    }
    return total;
}

JavaScript

var findNumberOfLIS = function(nums) {
    const n = nums.length;
    const len = new Array(n).fill(1);
    const count = new Array(n).fill(1);
    let best = 1;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    count[i] = count[j];
                } else if (len[j] + 1 === len[i]) {
                    count[i] += count[j];
                }
            }
        }
        if (len[i] > best) best = len[i];
    }
    let total = 0;
    for (let i = 0; i < n; i++) {
        if (len[i] === best) total += count[i];
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming