NearestElement.java

package com.thealgorithms.stacks;

import java.util.Stack;

/**
 * Implements classic stack-based algorithms to find nearest elements.
 *
 * Algorithms included:
 * 1. Nearest Greater to Right
 * 2. Nearest Greater to Left
 * 3. Nearest Smaller to Right
 * 4. Nearest Smaller to Left
 */
public final class NearestElement {
    // Private constructor to prevent instantiation
    private NearestElement() {
    }

    /** Finds the nearest greater element to the right for each element in the array. */
    public static int[] nearestGreaterToRight(int[] arr) {
        if (arr == null) {
            throw new IllegalArgumentException("Input array cannot be null");
        }

        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }

        return result;
    }

    /** Finds the nearest greater element to the left for each element in the array. */
    public static int[] nearestGreaterToLeft(int[] arr) {
        if (arr == null) {
            throw new IllegalArgumentException("Input array cannot be null");
        }

        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }

        return result;
    }

    /** Finds the nearest smaller element to the right for each element in the array. */
    public static int[] nearestSmallerToRight(int[] arr) {
        if (arr == null) {
            throw new IllegalArgumentException("Input array cannot be null");
        }

        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }

        return result;
    }

    /** Finds the nearest smaller element to the left for each element in the array. */
    public static int[] nearestSmallerToLeft(int[] arr) {
        if (arr == null) {
            throw new IllegalArgumentException("Input array cannot be null");
        }

        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }

        return result;
    }
}