Crack the Backend

Problem Statement

You are given a circular integer array nums. For each element, find the next greater number: the first number to its right that is strictly greater, with the array treated as circular (so after the last element we wrap to the first). Return an array where answer[i] is the next greater number for nums[i], or -1 if none exists.

Key Observations

Monotonic stack (decreasing), two passes: The same logic as NGE I: when we see a value greater than the stack top, the stack top's NGE is that value. To handle circularity, we traverse indices 0..2*n-1 using idx = i % n. So we process each element twice; the second pass assigns NGEs for elements whose "next greater" wraps around. We only push indices in the first pass i < n to avoid double-pushing; when we pop we assign result[popped] = nums[idx].

Approach

High-level: Stack of indices. For i = 0 to 2*n-1: idx = i % n; while stack not empty and nums[stack.peek()] < nums[idx], result[stack.pop()] = nums[idx]; if i < n push i. Initialize result with -1.

Steps: int n = nums.length; int[] res = new int[n]; Arrays.fill(res, -1); Deque<Integer> st; for (int i = 0; i < 2*n; i++) { int idx = i % n; while (!st.isEmpty() && nums[st.peek()] < nums[idx]) res[st.pop()] = nums[idx]; if (i < n) st.push(i); } return res.

Implementation

Java

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;

        while (!st.isEmpty() && nums[st.peek()] < nums[idx]) {
            result[st.pop()] = nums[idx];
        }

        if (i < n) {
            st.push(idx);
        }
    }

    return result;
}

Test Cases

Example 1

Input

nums = [1,2,1]

Expected

[2,-1,2]

Explanation

Circular next greater.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.