Next Greater Element - 2

Medium

Walk the array twice for the wrap-around

Problem

Find the next greater element for each item in a circular array.

In simple words

Loop the array twice with a stack of waiting indices so elements can find a bigger value that wraps around.

The idea

In a circular array an element's answer may lie before it, so iterate 2n times using index modulo n while only pushing during the first pass. The second pass resolves anything still waiting without duplicating entries.

The trick

Index with `i % n` and run i from 0 to 2n-1.
Only push indices during the first pass, or you will answer elements twice.

←→stepspaceplay

1/13

Brute force

timeO(n²)spaceO(1)

Circular scan.

1for (let i = 0; i < n; i++)2  for (let s = 1; s < n; s++)3    if (nums[(i + s) % n] > nums[i]) { res[i] = nums[(i + s) % n]; break; }4return res;

Input

array: [1, 2, 3, 4, 3]

Memory

i: —
j: —

Output

done: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [1, 2, 1]
Output:: [2, -1, 2]
Explanation:: Wrapping around, the last 1 sees the 2.

Example 2

Input:: nums = [1, 2, 3, 4, 3]
Output:: [2, 3, 4, -1, 4]
Explanation:: 4 has no greater even around → -1.

Example 3

Input:: nums = [5, 4, 3, 2, 1]
Output:: [-1, 5, 5, 5, 5]
Explanation:: Each looks around for something bigger.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.