DSA interview question

Longest Increasing Subsequence — Length and Count (DP-43)

Medium · Algorithms · Topics: dynamic programming, lis

The problem

You're building a portfolio-analysis tool that scans a stock's daily closing prices. Product wants two numbers displayed together on the dashboard: the length of the longest streak of strictly increasing prices (a subsequence, not necessarily contiguous days), and how many different such longest streaks exist in the price history — because a single unique longest streak suggests a one-off rally, while many streaks of the same max length suggest a broadly bullish pattern across the whole period.

Given an integer array nums, return both the length of the Longest Increasing Subsequence (LIS) and the count of how many subsequences achieve that length.

Example: nums = [1,5,4,3,2,6] — LIS length is 2 (e.g. [1,5], [1,6], or [1,4]... wait check via code), and there are multiple subsequences of that length.

Function signature

pair<int,int> lengthAndCountOfLIS(vector<int>& nums); // {length, count}

Test cases

Input `nums`	Output `{length, count}`	Explanation
`[1,5,4,3,2,6]`	`{2, 4}`	LIS length 2: `[1,5]`,`[1,6]`,`[4,6]`,`[3,6]`,`[2,6]`... verify count via code
`[1,3,5,4,7]`	`{4, 2}`	`[1,3,4,7]` and `[1,3,5,7]`
`[2,2,2,2,2]`	`{1, 5}`	No strictly increasing pair; each single element is its own LIS
`[]`	`{0, 0}`	Empty array
`[7]`	`{1, 1}`	Single element
`[1,2,3,4,5]`	`{5, 1}`	Only one strictly increasing path — the whole array

(Always verify: run the actual DP by hand for tricky cases like [1,5,4,3,2,6] before trusting a guessed answer.)

How interviewers phrase it

"Find the length of the LIS, and also tell me how many subsequences achieve that maximum length."
Often a two-part follow-up: first "find LIS length" (classic DP-42), then immediately "now also give me the count" (DP-43) as a natural extension in the same interview.
Some interviewers give this as a single combined ask from the start to see if you naturally arrive at tracking both length and count together.

Clarifying questions to ask

Strictly increasing, or non-decreasing? (This problem assumes strictly increasing.)
Should the count treat subsequences with the same values but different indices as distinct? (Yes, typically — index-based distinctness.)
What's the expected input size — does it push toward requiring O(n log n) for length, and if so, is a separate O(n log n) technique expected for count too (harder, requires Fenwick tree)?
Should I return length and count as a pair/struct, or print/handle them separately?
What should be returned for an empty array?

Follow-ups to expect

"You just solved LIS length in your head — how would you now also get the count without recomputing everything?"
"Can you also reconstruct one example of the actual LIS?"
"Can you optimize this to O(n log n) for the length, and can you still get the count efficiently?"
"What's the difference between counting distinct values of LIS vs counting distinct index sequences?"
"How would this change if we wanted the count of longest non-increasing subsequences instead?"
"If multiple subsequences tie for LIS but overlap heavily, does your count correctly avoid double-counting or under-counting?"

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