The O(n) Club: Next Greater Element II: When Arrays Forget Where Home Is

The O(n) Club: Next Greater Element II—When Arrays Forget Where Home Is

⚡ TL;DR

Find the next greater number for each element in a circular array. Wrap around if you must. Brute force will fry your CPU, but hey, it works (technically):

// Not for production, or your sanity!
public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            int idx = (i + j) % n;
            if (nums[idx] > nums[i]) {
                res[i] = nums[idx];
                break;
            }
        }
    }
    return res;
}

🧠 How Devs Usually Mess This Up

You see “next greater element” and start coding like a Java ninja—until the last few elements, when logic faints and circularity bites. Common mistakes include:

• Forgetting about the circular array—your code stops at the end, but the problem doesn’t.
• Pushing actual values onto the stack instead of indices. Values don’t tell you where to write the answer, so eventually, no one gets what they want.
• Using O(n²) brute force, which is fine for sample tests, but please—think of the servers!

🔍 What’s Actually Going On

Picture your array as a circular necklace at a Java developer’s vintage party. Every bead (element) is curious: who’s the next brighter bead? If you have to walk past the clasp and loop all the way around, so be it. The monotonic stack is the bouncer who keeps out-of-order beads in line, popping anyone when a flashier one approaches.

So, we scan the array twice (because if you’ve walked a circular necklace once, apparently there’s still more fun). We keep track of indices with unsatisfied dreams—err, no greater number found yet. Cruelly, some beads never find happiness (get -1).

🛠️ PseudoCode

• Initialize res[] to -1 and an empty stack.
• For i from 0 to 2 * n - 1:
  • Let num = nums[i % n] (keeps you on the circular rollercoaster).
  • While stack not empty and nums[stack.peek()] < num:
    • res[stack.pop()] = num
  • If i < n, push i onto stack (store indices for original elements only).
• Return res (unresolved dreams remain -1).

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Off-By-One loops: Stop at 2 * n, not a random multiple—it matters!
• Circular Misfire: Forgetting i % n leaves some elements homeless.
• Brute-force Sadness: Code looks fine for 3 elements, falls apart on 30,000.
• Space Oopsies: Stack only needs to be as deep as your unsatisfied beads (n at most).
• All elements the same? Output will be -1 for everyone—the Java version of a ghost party.

🧠 Interviewer Brain-Tattoo

Remember: Whenever an interviewer says “circular,” double your loop, bring your stack, and don’t let indices wander off unsupervised. Arrays and job offers will thank you.