Next Greater Element II - Practice Coding Problems

Next Greater Element II - Problem

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Input & Output

Example 1 — Basic Circular Array

$ Input: nums = [1,2,1]

› Output: [2,-1,2]

💡 Note: For nums[0]=1, next greater is 2. For nums[1]=2, no greater element exists (-1). For nums[2]=1, wrapping around, next greater is 2.

Example 2 — All Elements Have Next Greater

$ Input: nums = [1,2,3,4,3]

› Output: [2,3,4,-1,4]

💡 Note: nums[0]=1→2, nums[1]=2→3, nums[2]=3→4, nums[3]=4 has no greater (-1), nums[4]=3 wraps to find 4.

Example 3 — Single Element

$ Input: nums = [5]

› Output: [-1]

💡 Note: Only one element, no next greater element possible in circular array.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array [1,2,1] where last connects to first

Process

For each element, find next greater circularly

Output

Result [2,-1,2] showing next greater for each position

Key Takeaway

🎯 Key Insight: A monotonic stack processes each element at most twice to efficiently find next greater elements in circular arrays

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is using a monotonic stack to efficiently find next greater elements in a circular array. Best approach is the monotonic stack with double iteration: Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack	O(n)	O(n)	Use a stack to efficiently track elements waiting for their next greater element
Brute Force - Double Loop	O(n²)	O(1)	For each element, scan circularly to find the next greater element

Monotonic Stack — Algorithm Steps

Initialize result array with -1 and an empty stack
Process array twice (2n iterations) to handle circular nature
For each element, pop from stack all smaller elements and set their result
Push current element index to stack if in first pass

Visualization

Tap to expand

Step-by-Step Walkthrough

Process twice

Iterate through array twice for circularity

Stack operations

Pop smaller elements when greater found

Resolve elements

Set next greater element for popped indices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)malloc(numsSize * sizeof(int));
    int* stack = (int*)malloc(numsSize * sizeof(int));
    int stackTop = -1;
    
    // Initialize result with -1
    for (int i = 0; i < numsSize; i++) {
        result[i] = -1;
    }
    
    // Process the array twice to handle circularity
    for (int i = 0; i < 2 * numsSize; i++) {
        // While stack is not empty and current element is greater than
        // the element at the index stored at top of stack
        while (stackTop >= 0 && nums[i % numsSize] > nums[stack[stackTop]]) {
            int idx = stack[stackTop--];
            result[idx] = nums[i % numsSize];
        }
        
        // Only push indices during the first pass
        if (i < numsSize) {
            stack[++stackTop] = i;
        }
    }
    
    free(stack);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped from stack at most once across 2n iterations

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n elements in worst case (decreasing array)

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler