Number of Longest Increasing Subsequence

Medium · 1-D Dynamic Programming · Explanation and code example

Dynamic Programming (Binary Search + Prefix Sum)

How it works

The O(n^2) DP solution can be optimized by using binary search and prefix sums. The key insight is to organize elements by the length of the longest increasing subsequence ending at them. For each length, we maintain a list of elements sorted in decreasing order along with cumulative counts. When processing a new element, we use binary search to find where it fits and to count how many subsequences of the previous length can be extended by this element.

Steps

  1. Initialize dp as a list of lists, where dp[len] contains pairs (value, cumulative_count) representing elements that end an increasing subsequence of length len+1.
  2. For each element in the array:
    • Use binary search (bs1) to find the longest subsequence length this element can extend.
    • Use binary search (bs2) on the previous length's list to count how many subsequences can be extended (those with values less than the current element).
    • If this element extends the maximum length, create a new entry in dp.
    • Otherwise, append the element to the appropriate length bucket with updated cumulative count.
  3. The answer is the cumulative count in the last entry of the longest length bucket.

Complexity

  • Time complexity: O(nlog n)
  • Space complexity: O(n)

Things to watch for

Only Counting LIS Length Without Tracking Count

This problem requires counting how many subsequences achieve the maximum length, not just finding the length itself. A common mistake is to reuse standard LIS code that only tracks length. You must maintain both the length and the count of subsequences reaching that length at each position.

Resetting Count Instead of Accumulating

When finding a subsequence of the same maximum length, you should add to the count, not reset it. Only reset the count when you find a strictly longer subsequence. Confusing these cases leads to undercounting valid subsequences.

Using Non-Strict Inequality for Increasing Check

The problem asks for strictly increasing subsequences. Using nums[j] >= nums[i] instead of nums[j] > nums[i] will incorrectly include equal elements, leading to wrong answers on inputs with duplicate values.

Python code example

from typing import List

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[[0, 0], [nums[0], 1]]]

        def bs1(num):
            l, r = 0, len(dp) - 1
            j = len(dp) - 1
            while l <= r:
                mid = (l + r) // 2
                if dp[mid][-1][0] < num:
                    l = mid + 1
                else:
                    j = mid
                    r = mid - 1
            return j

        def bs2(i, num):
            if i < 0:
                return 1
            l, r = 1, len(dp[i]) - 1
            j = 0
            while l <= r:
                mid = (l + r) // 2
                if dp[i][mid][0] >= num:
                    j = mid
                    l = mid + 1
                else:
                    r = mid - 1
            return dp[i][-1][1] - dp[i][j][1]

        LIS = 1
        for i in range(1, n):
            num = nums[i]
            if num > dp[-1][-1][0]:
                count = bs2(LIS - 1, num)
                dp.append([[0, 0], [num, count]])
                LIS += 1
            else:
                j = bs1(num)
                count = bs2(j - 1, num)
                dp[j].append([num, dp[j][-1][1] + count])

        return dp[-1][-1][1]

C++ code example

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        vector<vector<pair<int, int>>> dp = {{{0, 0}, {nums[0], 1}}};
        int LIS = 1;

        for (int i = 1; i < nums.size(); i++) {
            int num = nums[i];
            if (num > dp.back().back().first) {
                int count = bs2(dp, LIS - 1, num);
                dp.push_back({{0, 0}, {num, count}});
                LIS++;
            } else {
                int j = bs1(dp, num);
                int count = bs2(dp, j - 1, num);
                dp[j].push_back({num, dp[j].back().second + count});
            }
        }

        return dp.back().back().second;
    }

private:
    int bs1(vector<vector<pair<int, int>>>& dp, int num) {
        int l = 0, r = dp.size() - 1, j = dp.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (dp[mid].back().first < num) {
                l = mid + 1;
            } else {
                j = mid;
                r = mid - 1;
            }
        }
        return j;
    }

    int bs2(vector<vector<pair<int, int>>>& dp, int i, int num) {
        if (i < 0) return 1;
        int l = 1, r = dp[i].size() - 1, j = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (dp[i][mid].first >= num) {
                j = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return dp[i].back().second - dp[i][j].second;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations