DSA interview question

Longest Increasing Subsequence

Medium · Algorithms · Topics: dynamic programming, lis, binary search

The problem

You're working on a stock analytics dashboard. A product manager wants a feature that highlights the longest streak of days where a stock's closing price could be picked (not necessarily consecutive days) such that the prices strictly increase — this helps visualize the "best possible uptrend" a trader missed. Given an array of daily closing prices nums, you need to return the length of the longest strictly increasing subsequence (LIS).

Note: it's a subsequence, not a subarray — elements don't need to be contiguous, just in relative order.

Function signature

int lengthOfLIS(vector<int>& nums);

Test cases

Input `nums`	Output	Explanation
`[10,9,2,5,3,7,101,18]`	4	LIS is `[2,3,7,101]` or `[2,3,7,18]`
`[0,1,0,3,2,3]`	4	LIS is `[0,1,2,3]`
`[7,7,7,7,7,7,7]`	1	Strictly increasing → duplicates don't count
`[1]`	1	Single element
`[]`	0	Empty array
`[4,10,4,3,8,9]`	3	LIS is `[4,8,9]`
`[1,2,3,4,5]`	5	Already fully increasing

(Always clarify "strictly increasing" vs "non-decreasing" before coding — it changes comparator logic.)

How interviewers phrase it

"Given an array of integers, find the length of the longest strictly increasing subsequence."
"What's the longest run of numbers you can pick, in order, that keep increasing?"
Sometimes disguised as: "Find the minimum number of deletions to make the array sorted (increasing)." → n - LIS.

Clarifying questions to ask

Strictly increasing, or non-decreasing (duplicates allowed)? This changes the comparator (< vs <=) in the binary search step.
Do I need to return just the length, or also reconstruct the actual subsequence?
What's the expected size of nums? (If n up to 10^5, O(n²) DP will TLE — signals need for O(n log n).)
Can the array contain negative numbers or duplicates?

Follow-ups to expect

"Can you do better than O(n²)?"
"Can you reconstruct the actual LIS, not just its length?"
"What if it's non-decreasing instead of strictly increasing?"
"Can you find the number of distinct LIS's?"
"What if you needed the Longest Common Subsequence between two arrays instead?"
"Can you solve it in O(n) if the array is nearly sorted / has special structure?"

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