Next Greater Element — O(n²) Timed Out at 10k Updates/sec

public class NextGreaterElementBruteForce {

    /**
     * For each element, scan rightward to find the first element
     * that is strictly greater. Returns -1 if none exists.
     *
     * Time:  O(n^2) — nested loops over the array
     * Space: O(n)   — result array
     */
    public static int[] findNextGreaterBruteForce(int[] prices) {
        int totalElements = prices.length;
        int[] nextGreater = new int[totalElements];

        for (int currentIndex = 0; currentIndex < totalElements; currentIndex++) {
            // Assume no greater element exists to the right
            nextGreater[currentIndex] = -1;

            // Scan every element to the right of currentIndex
            for (int lookAheadIndex = currentIndex + 1; lookAheadIndex < totalElements; lookAheadIndex++) {
                if (prices[lookAheadIndex] > prices[currentIndex]) {
                    // Found the first greater element — record it and stop scanning
                    nextGreater[currentIndex] = prices[lookAheadIndex];
                    break;
                }
            }
        }
        return nextGreater;
    }

    public static void main(String[] args) {
        int[] stockPrices = {73, 74, 75, 71, 69, 72, 76, 73};

        int[] result = findNextGreaterBruteForce(stockPrices);

        System.out.println("Stock Price  →  Next Greater Price");
        System.out.println("-------------------------------------");
        for (int i = 0; i < stockPrices.length; i++) {
            String nextVal = result[i] == -1 ? "none" : String.valueOf(result[i]);
            System.out.printf("    %-6d   →      %s%n", stockPrices[i], nextVal);
        }
    }
}

import java.util.Arrays;
import java.util.Stack;

public class NextGreaterElementStack {

    /**
     * Uses a monotonic decreasing stack to find the next greater element
     * for every position in a single left-to-right pass.
     *
     * Time:  O(n) — each element is pushed and popped at most once
     * Space: O(n) — stack can hold at most n elements (e.g. descending input)
     */
    public static int[] findNextGreater(int[] temperatures) {
        int totalDays = temperatures.length;
        int[] nextWarmerTemp = new int[totalDays];

        // Fill with -1 as the default: "no warmer day found"
        Arrays.fill(nextWarmerTemp, -1);

        // Stack holds INDICES (not values) so we can update the result array
        Stack<Integer> waitingIndices = new Stack<>();

        for (int today = 0; today < totalDays; today++) {

            // While today's temperature beats the temperature at the top of the stack...
            while (!waitingIndices.isEmpty()
                    && temperatures[today] > temperatures[waitingIndices.peek()]) {

                // ...the day on top of the stack has found its answer: today's temperature
                int resolvedDay = waitingIndices.pop();
                nextWarmerTemp[resolvedDay] = temperatures[today];
            }

            // Today hasn't found ITS next greater yet — add it to the waiting list
            waitingIndices.push(today);
        }

        // Any index still in the stack had no greater element to its right — stays -1
        return nextWarmerTemp;
    }

    public static void main(String[] args) {
        // Real-world framing: daily temperatures, find the next warmer day's temperature
        int[] dailyTemperatures = {73, 74, 75, 71, 69, 72, 76, 73};

        int[] result = findNextGreater(dailyTemperatures);

        System.out.println("Day  │ Temp │ Next Greater Temp");
        System.out.println("─────┼──────┼──────────────────");
        for (int day = 0; day < dailyTemperatures.length; day++) {
            String answer = result[day] == -1 ? "none" : String.valueOf(result[day]);
            System.out.printf(" %-3d │  %-3d │  %s%n", day + 1, dailyTemperatures[day], answer);
        }
    }
}

import java.util.Arrays;
import java.util.Stack;

public class NextGreaterElementCircular {

    /**
     * Finds the next greater element in a circular array.
     * Elements wrap around: after the last element, search continues from index 0.
     *
     * Technique: iterate 0 to 2n-1, use (index % n) to wrap around.
     *            Only push indices during the first pass (index < n).
     *
     * Time:  O(n) — each element is pushed/popped at most once across both passes
     * Space: O(n) — stack size
     */
    public static int[] findNextGreaterCircular(int[] circularPrices) {
        int size = circularPrices.length;
        int[] nextGreater = new int[size];
        Arrays.fill(nextGreater, -1);

        Stack<Integer> waitingIndices = new Stack<>();

        // We loop 2*size to simulate wrapping around the array
        for (int iteration = 0; iteration < 2 * size; iteration++) {

            // Wrap the iteration index back into a valid array index
            int wrappedIndex = iteration % size;

            // Resolve all waiting elements that the current element is greater than
            while (!waitingIndices.isEmpty()
                    && circularPrices[wrappedIndex] > circularPrices[waitingIndices.peek()]) {
                int resolvedIndex = waitingIndices.pop();
                nextGreater[resolvedIndex] = circularPrices[wrappedIndex];
            }

            // Only push during the first full pass — second pass is for resolution only
            if (iteration < size) {
                waitingIndices.push(wrappedIndex);
            }
        }

        return nextGreater;
    }

    public static void main(String[] args) {
        // In a circular market: after price[last], the search continues from price[0]
        int[] circularMarketPrices = {5, 4, 3, 2, 1};

        int[] result = findNextGreaterCircular(circularMarketPrices);

        System.out.println("Circular Array: [5, 4, 3, 2, 1]");
        System.out.println();
        System.out.println("Price  │  Next Greater (circular)");
        System.out.println("───────┼──────────────────────────");
        for (int i = 0; i < circularMarketPrices.length; i++) {
            String answer = result[i] == -1 ? "none" : String.valueOf(result[i]);
            System.out.printf("  %-4d │  %s%n", circularMarketPrices[i], answer);
        }
    }
}

import java.util.Arrays;
import java.util.Stack;

public class DaysUntilWarmerTemperature {

    /**
     * For each day, returns how many days you have to wait until a warmer temperature.
     * If no warmer temperature ever comes, the answer for that day is 0.
     *
     * This is LeetCode 739 — one of the most common Next Greater Element interview variants.
     *
     * Time:  O(n)
     * Space: O(n)
     */
    public static int[] daysUntilWarmer(int[] dailyTemps) {
        int totalDays = dailyTemps.length;
        int[] waitDays = new int[totalDays]; // default 0 means "never gets warmer"

        Stack<Integer> waitingDayIndices = new Stack<>();

        for (int today = 0; today < totalDays; today++) {

            // Today's temp resolves all past days that were waiting for something warmer
            while (!waitingDayIndices.isEmpty()
                    && dailyTemps[today] > dailyTemps[waitingDayIndices.peek()]) {

                int coldDay = waitingDayIndices.pop();

                // KEY DIFFERENCE from the value variant:
                // Store the GAP between the two days, not the temperature itself
                waitDays[coldDay] = today - coldDay;
            }

            waitingDayIndices.push(today);
        }

        // Days still in the stack never found a warmer day — waitDays stays 0
        return waitDays;
    }

    public static void main(String[] args) {
        int[] weekTemperatures = {73, 74, 75, 71, 69, 72, 76, 73};

        int[] daysToWait = daysUntilWarmer(weekTemperatures);

        System.out.println("Day  │ Temp │ Days Until Warmer");
        System.out.println("─────┼──────┼───────────────────");
        for (int day = 0; day < weekTemperatures.length; day++) {
            String wait = daysToWait[day] == 0 ? "never" : daysToWait[day] + " day(s)";
            System.out.printf(" %-3d │  %-3d │  %s%n", day + 1, weekTemperatures[day], wait);
        }
    }
}