DSA interview question

Next Smaller Element

Medium · Data structures · Topics: stack, monotonic stack

The problem

A retailer tracks daily prices for a product and, for each day, wants to know the next day with a strictly lower price (reporting that price, or −1 if it never drops lower), so the tool can show "wait for a drop" advice. It's the mirror image of the next greater element: scan from the right with a stack of candidates, but now pop every candidate that is ≥ the current price. What remains on top is the nearest smaller value.

Example: [4, 8, 5, 2, 25] → [2, 5, 2, -1, -1].

Function signature

vector<int> nextSmallerElements(const vector<int>& a);  // -1 where none exists to the right

Test cases

Input	Output	Explanation
`[4, 8, 5, 2, 25]`	`[2, 5, 2, -1, -1]`
`[13, 7, 6, 12]`	`[7, 6, -1, -1]`
`[1, 2, 3]`	`[-1, -1, -1]`	Increasing
`[3, 2, 1]`	`[2, 1, -1]`
`[2, 2, 1]`	`[1, 1, -1]`	Strictly smaller: an equal value doesn't count

(Confirm: nearest element to the right that is strictly smaller; the answer is its value, or −1.)

How interviewers phrase it

"For every element, find the next smaller element to its right" (GeeksforGeeks "Next Smaller Element").
The previous-smaller and next-smaller arrays are building blocks for "largest rectangle in a histogram" and "sum of subarray minimums".

Clarifying questions to ask

Strictly smaller or smaller-or-equal?
Values or indices?
Is the array circular?

Follow-ups to expect

"Why pop elements ≥ the current one?"
"What does the stack look like?"
"How do you get the previous smaller element?"
"How do these arrays help with histograms?"
"Complexity?"

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