290. Next Smaller Element for Every Array Element

Given an array of n integers, for every element find the first element to its right that is strictly smaller than it. Print these values in order, space-separated, using -1 wherever no such element exists.

Input: The first line contains an integer n. The second line contains n space-separated integers representing the array. Output: Print n space-separated integers - the next smaller element to the right of each element, or -1 where none exists.

1 <= n <= 10^5

Whenever a problem asks for 'the next element satisfying some comparison', a right-to-left scan with a monotonic stack (discarding candidates that violate the needed monotonic order as you go) is almost always the efficient approach - internalizing this single template covers a whole family of similar problems.

For every element in an array, find the first element to its RIGHT that's strictly smaller than it. Brute force: For every element, scan everything to its right directly looking for the first smaller value - this costs O(n²), too slow for large arrays. Optimised: This is the exact mirror image of 'Next Greater Element' - the same monotonic-stack technique, just with the comparison direction flipped (popping GREATER-OR-EQUAL elements instead of smaller-or-equal ones), still giving O(n) total work.

Build a sparse table supporting O(1) range-minimum queries over the array. Then for each index i, binary search over the range (i, n-1] for the smallest index j such that the minimum of arr[i+1..j] is strictly less than arr[i] - since the range minimum is monotonically non-increasing as the range extends, binary search correctly locates the first position where a smaller element appears, verified in O(1) per check via the sparse table. This is a genuinely different technique from a monotonic stack, turning the problem into a build-once, query-with-binary-search structure, though the O(n log n) build and per-query cost is more expensive than necessary. Time: O(n log n) Space: O(n log n)

Traverse the array from right to left while maintaining a stack of candidate 'next smaller' values in increasing order from top to bottom: before processing each element, pop any stack values that are greater than or equal to it (they can never be the answer for anything further left, since the current, closer element is smaller), then the new top of the stack (if any) is the current element's answer, and finally push the current element. Because each element is pushed and popped from the stack at most once across the whole traversal, the total work is linear despite each individual element look-back being unbounded in the worst case. Time: O(n) Space: O(n)

For every element, scan forward through all elements to its right until a strictly smaller value is found (or the end of the array is reached, in which case the answer is -1). This is a direct implementation of the definition, but each element potentially triggers a full rightward scan, so pairs of elements far apart with no smaller value between them cost O(n) each to resolve. Time: O(n^2) Space: O(1)

1. Scan the array from RIGHT to LEFT, maintaining a stack of candidates that could still be a next-smaller-element for something further left. 2. Before processing each element, pop everything from the stack that's GREATER THAN OR EQUAL to it - those can never be the answer for anything further left. 3. Whatever remains on top of the stack (or -1 if empty) is this element's answer; push the current element for future comparisons.

Time: O(n) - each element is pushed and popped from the stack at most once. Space: O(n) in the worst case, for the stack.

n = 1 (answer is -1); a strictly increasing array (every answer is -1); a strictly decreasing array (every answer is the immediate next element); n up to 10^5 for performance.

Be ready to state clearly that this is simply 'Next Greater Element' with the comparison flipped - recognizing this mirror relationship instantly, rather than re-deriving the technique from scratch, is a strong signal.