DSA interview question

Number of Longest Increasing Subsequences

Medium · Algorithms · Topics: dynamic programming, lis

The problem

You're building an analytics feature for a stock-tracking app. Users want to know not just the length of the longest streak of strictly increasing prices in their price history, but how many distinct such longest streaks exist — because if there are many, the trend is "robust" (many paths show growth), and if there's only one, it might be a fragile/coincidental pattern worth flagging differently in the UI.

Given an integer array nums, return the number of longest strictly increasing subsequences (not the LIS itself, just the count of how many subsequences achieve that maximum length).

Example: nums = [1,3,5,4,7] — the longest increasing subsequences have length 3: [1,3,5,7]... wait, that's length 4. Let's verify: [1,3,4,7] and [1,3,5,7] are both length 4. So the answer is 2.

Function signature

int findNumberOfLIS(vector<int>& nums);

Test cases

Input `nums`	Output	Explanation
`[1,3,5,4,7]`	2	`[1,3,4,7]` and `[1,3,5,7]` both have length 4
`[2,2,2,2,2]`	5	No increasing subsequence longer than length 1; each single element counts
`[1,2,4,3,5,4,7,2]`	3	Multiple length-5 increasing subsequences exist — verify via dry run
`[]`	0	Empty array — no subsequences exist
`[7]`	1	Single element — one subsequence of length 1
`[1,2,3,4,5]`	1	Only one strictly increasing path (the whole array)

(Always verify: are duplicates and single-element arrays handled correctly before coding.)

How interviewers phrase it

"Given an array, find how many longest increasing subsequences exist — not the LIS itself, just the count."
"This builds on the classic LIS problem — have you solved 'Longest Increasing Subsequence' before? Good, now count them."
They may first ask you to solve plain LIS (length only) as a warm-up before adding the counting twist.

Clarifying questions to ask

Does "increasing" mean strictly increasing, or non-decreasing (allowing equal adjacent values)? (This problem is strictly increasing — confirm.)
Should I count subsequences by their values/positions, or just by distinct value patterns? (E.g., duplicate values at different indices count as different subsequences.)
What's the expected size of nums? (If large, e.g. 1e5, signals need for O(n log n) approach instead of O(n²).)
Can the array contain negative numbers or duplicates?
What should I return for an empty array?

Follow-ups to expect

"Can you also return one example of the actual longest increasing subsequence, not just the count?"
"Can you optimize this to O(n log n)?"
"What if we want non-decreasing subsequences instead of strictly increasing?"
"How does this relate to plain LIS (length only)?"
"What if the array is a stream (online), can you maintain this incrementally?"
"Can you do this with recursion + memoization instead of bottom-up tabulation?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview