Number of Longest Increasing Subsequence

Number of Longest Increasing Subsequence

What is this problem about?

The Number of Longest Increasing Subsequence problem asks you to not just find the length of the longest increasing subsequence (LIS), but count how many distinct LIS exist in the array. This Number of Longest Increasing Subsequence coding problem extends the classic LIS problem by maintaining both the length and the count of ways to achieve that length at each position.

Why is this asked in interviews?

Microsoft, Meta, Amazon, TikTok, and Google ask this because it builds directly on LIS intuition while adding a counting layer. Candidates who only know the O(n²) LIS often forget to track the count, making this a strong differentiator. The array, binary indexed tree, segment tree, and dynamic programming interview pattern is the core, with an extension to binary indexed trees for the O(n log n) solution.

Algorithmic pattern used

Two-array DP. Maintain dp[i] = length of LIS ending at index i, and count[i] = number of such subsequences. For each i, scan all j < i where arr[j] < arr[i]: if dp[j]+1 > dp[i], update dp[i] and reset count[i] = count[j]. If dp[j]+1 == dp[i], add count[i] += count[j]. Answer = sum of count[i] for all i where dp[i] == maxLen.

Example explanation

Array: [1, 3, 5, 4, 7].

• dp = [1,2,3,3,4], count = [1,1,1,1,2] (two ways to reach length 4: [1,3,5,7] and [1,3,4,7]). Max LIS length = 4. Sum of counts where dp[i]=4: count[4]=2. Answer = 2.

Common mistakes candidates make

• Tracking only dp (length) without the count array.
• Not resetting count[i] when a strictly longer path is found (should replace, not add).
• Adding count[j] when dp[j]+1 < dp[i] (only add when equal length found).
• Off-by-one in computing maxLen from the dp array.

Interview preparation tip

Always approach LIS variants by asking: "What additional information per state do I need?" Here, adding a count array answers the "how many" question. Practice extending LIS to other variants: longest non-decreasing subsequence, LIS with cost, LIS count. Each adds a new dimension to the same DP framework. For O(n log n) count solution, use a Fenwick tree or segment tree indexed by value to maintain both max_length and sum_count efficiently.