Pro

86. Next Greater Element Using Monotonic Stack

Easy

Problem Description

Given an array of $N$ integers, find the Next Greater Element (NGE) for each element. The NGE for an element $x$ is the first greater element to its right. If no greater element exists to its right, output -1.

Input Format

•Line 1: An integer $N$ ( $1 \le N \le 10^5$ ).
•Line 2: $N$ space-separated integers $A_1, \dots, A_N$ .

Output Format

Print $N$ space-separated integers representing the next greater element for each index.

Example 1:

Input:

4
4 5 2 25

Output:

5 25 25 -1

Explanation: Next greater for 4 is 5; for 5 is 25; for 2 is 25; for 25 none (-1).

Example 2:

Input:

4
13 7 6 12

Output:

-1 12 12 -1

Explanation: Next greater for 7 is 12; for 6 is 12; 13 and 12 have none.

Example 3:

Input:

3
1 2 3

Output:

2 3 -1

Explanation: Strictly increasing sequence.

Constraints:

Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
Time complexity target: O(N) or O(N log N) where applicable.
Auxiliary space target: O(1) or minimal auxiliary memory.

Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?

1,180 Online

Code

Loading Code Editor...

SavedLn 1, Col 1

param_1 =

param_2 =

Sandboxed Engine

Ctrl+Enter = Run | Ctrl+Shift+Enter = Submit