160. Next Greater Element for Every Array Element

Given an array of n integers, for every element find the first element to its right that is strictly greater 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, the array. Output: Print n space-separated integers - each element's next greater element to its right, or -1 if none exists.

1 <= n <= 10^5

This 'monotonic stack' pattern (maintaining a stack where popping happens when a new element breaks the monotonic order) reappears constantly in this category - Stock Span, Next Smaller Element, Largest Rectangle in Histogram, and Longest Valid Parentheses all use variations of this exact idea.

For every element in an array, find the first element to its RIGHT that's strictly bigger than it. Brute force: For every element, scan everything to its right directly looking for the first bigger value - this costs O(n²), too slow for large arrays. Optimised: Maintaining a stack of 'still-unresolved' candidates while scanning right to left ensures each element is pushed and popped AT MOST ONCE across the whole algorithm - popping smaller elements permanently resolves them (they'll never be anyone's answer again), giving true O(n) total work despite looking like nested loops.

Scan the array from right to left maintaining a stack of candidate 'next greater' values kept in strictly decreasing order from bottom to top. For each element, pop off all stack values that are less than or equal to it (they can never be a next-greater for anything further left), then the new stack top (if any) is this element's answer; push the element and continue. Because each element is pushed and popped at most once across the whole scan, the total work is linear, which is optimal since the output itself requires examining every element. Time: O(n) Space: O(n)

Scan the array from right to left while maintaining a sorted structure (e.g. a balanced BST / ordered set) of all elements already seen to the right of the current position. For the current element, binary-search that structure for the smallest stored value strictly greater than it - that's its next greater element - then insert the current element into the structure before moving left. This replaces a full linear rescan per element with a logarithmic search, at the cost of maintaining a balanced sorted structure. Time: O(n log n) Space: O(n)

For every element, scan all elements to its right in order and stop at the first one that is strictly greater, recording it (or -1 if none is found). This directly implements the problem's definition and is trivially correct, but every element potentially triggers a full rightward scan. Time: O(n^2) Space: O(1) extra (excluding output)

1. Scan the array from RIGHT to LEFT, maintaining a stack of 'candidates' that could still be a next-greater-element for something further left. 2. Before processing each element, pop everything from the stack that's SMALLER THAN OR EQUAL to it - those popped values can never be the answer for anything further left (this current element is now a better, closer candidate). 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.

the array's last element, whose answer is always -1 since nothing lies to its right; a strictly decreasing array, where every answer is -1; n = 10^5 for performance.

Be ready to explain precisely WHY popping smaller-or-equal elements is safe (they can never be the answer for anything to their left, since the current element is closer AND at least as big) - this is the entire insight that makes the stack-based approach linear instead of quadratic.