DSA interview question

Print Longest Increasing Subsequence

Medium · Algorithms · Topics: dynamic programming, lis

The problem

You're extending the earlier stock-analytics dashboard feature. Product no longer just wants the length of the longest streak of increasing prices — they now want the actual list of prices that make up one such longest streak, so it can be highlighted directly on the price chart for the user.

Given an integer array nums, return the actual longest strictly increasing subsequence (any one valid instance if multiple exist), not just its length.

Example: nums = [10,9,2,5,3,7,101,18] — one valid longest increasing subsequence is [2,3,7,101] or [2,3,7,18], both length 4.

Function signature

vector<int> printLIS(vector<int>& nums);

Test cases

Input `nums`	Output (one valid answer)	Explanation
`[10,9,2,5,3,7,101,18]`	`[2,3,7,101]`	Length 4; `[2,3,7,18]` is also valid
`[0,1,0,3,2,3]`	`[0,1,2,3]`	Length 4
`[7,7,7,7,7]`	`[7]`	No strictly increasing pair — any single element
`[]`	`[]`	Empty array
`[5]`	`[5]`	Single element
`[1,2,3,4,5]`	`[1,2,3,4,5]`	Entire array is increasing

(Always confirm: output just needs to be a valid LIS, not necessarily unique — multiple correct answers may exist for the same input.)

How interviewers phrase it

"Now that you've found the length of the LIS, can you also print/return the actual subsequence?"
Often a direct follow-up after solving "Longest Increasing Subsequence" (length-only) in the same interview.
"Given an array, return one valid longest increasing subsequence — order matters, values should reflect an actual subsequence from the array."

Clarifying questions to ask

If multiple valid LIS of the same length exist, is any one acceptable, or is there a tie-break rule (e.g., lexicographically smallest, or leftmost occurring)?
Strictly increasing, or non-decreasing? (This problem assumes strictly increasing.)
Should I return indices into the original array, or just the values?
What's the expected size of nums? (Confirms whether O(n²) reconstruction is fine, or an O(n log n) approach with reconstruction is expected.)
What should be returned for an empty array — an empty vector, or is that not a valid test case?

Follow-ups to expect

"Can you do this in O(n log n) instead of O(n²)?"
"How does your reconstruction approach differ between the O(n²) and O(n log n) solutions?"
"What if there are multiple valid LIS of the same length — does your solution guarantee a specific one (e.g., lexicographically smallest)?"
"Can you print all distinct longest increasing subsequences, not just one?"
"How would you modify this for non-decreasing instead of strictly increasing?"
"Space complexity — can you print the LIS without storing a full parent array?"

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