Max Area in a Histogram using Stack

import java.util.*;

class maxArea  {

    public static void maxArea(int arr[]) { //O(n) - TC (most optimized code)

        int maxArea = 0;

        int nsr[] = new int[arr.length];

        int nsl[] = new int[arr.length];

       

        // Next Smaller Right

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

        // modified nextGreater code for NSR

        for(int i=arr.length-1; i>=0; i--) { // O(n)

            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) { // just change from <= to >= to find nextSmaller right

                s.pop();

            }

            if(s.isEmpty()) {

                //-1

                nsr[i] = arr.length;

               

            } else {

                //top

                nsr[i] = s.peek();

               

            }

            s.push(i);

        }

        // Next Smaller Left

        s = new Stack<>();

        for(int i=0; i<arr.length; i++) { // O(n)

            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) { // just change from <= to >= to find nextSmaller right

                s.pop();

            }

            if(s.isEmpty()) {

                //-1

                nsl[i] = -1;

               

            } else {

                //top

                nsl[i] = s.peek();

               

            }

            s.push(i);

        }

        // Current Area : width = j-i-1 = nsr[i]-nsl[i]-1 // O(n)

        for(int i=0; i<arr.length; i++) {

            int height = arr[i];

            int width = nsr[i] - nsl[i] - 1;

            int currArea = height * width;

            maxArea = Math.max(currArea, maxArea);

        }

        System.out.println("Max area in a histogram is: " + maxArea);

    }

    public static void main(String[] args) {

        int arr[] = {2, 1, 5, 6, 2, 3}; // heights in histogram

        maxArea(arr);

    }

} OUTPUT: Max area in a histogram is: 10