Brute Intuitive solution✔️✔️✅ Beats 98% Monotonic Pattern
503. Next Greater Element II\njava []\npublic class Solution {\n    public int[] nextGreaterElements(int[] A) {\n        int n = A.length;\n        int[] res = 
## 503. Next Greater Element II\n```java []\npublic class Solution {\n    public int[] nextGreaterElements(int[] A) {\n        int n = A.length;\n        int[] res = new int[n]; \n        Arrays.fill(res, -1); // Initialize result array with -1    \n        Stack<Integer> stack = new Stack<>(); // Stack to store indices\n\n        // Iterate through the array twice to handle circular nature\n        for (int i = 0; i < n * 2; i++) {       \n            // Use modulo to wrap around the array\n            while (!stack.isEmpty() && A[stack.peek()] < A[i % n]) {     \n                \n                res[stack.pop()] = A[i % n];\n            }\n            stack.push(i % n); // Push current index (mod n) onto the stack\n        }\n        return res; // Return the result array\n    }\n}\n\n```\n\nLearn Next Greater element, then next smaller element(**right**), previous smaller element (NSE **left**) its follow up questions notable 84. Largest Rectangle in Histogram and 85. Maximal Rectangle\n\n\n\n```java []\n//Next Greater Element\nimport java.util.Arrays;\nimport java.util.Stack;\n\npublic class NextGreaterElement {\n\n    public static int[] nextGreaterElement(int[] nums) {\n        int n = nums.length;\n        int[] result = new int[n];\n        Arrays.fill(result, -1);\n        Stack<Integer> stack = new Stack<>();\n\n        for (int i = 0; i < n; i++) {\n            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {\n                result[stack.pop()] = nums[i];\n            }\n            stack.push(i);\n        }\n\n        return result;\n    }\n\n    public static void main(String[] args) {\n        int[] nums = {4, 5, 2, 25};\n        int[] result = nextGreaterElement(nums);\n        System.out.println(Arrays.toString(result));  // Output: [5, 25, 25, -1]\n    }\n}\n\n```\n```java []\nimport java.util.Arrays;\nimport java.util.Stack;\n\npublic class PreviousGreaterElement {\n\n    public static int[] previousGreaterElement(int[] nums) {\n        int n = nums.length;\n        int[] result = new int[n];\n        Arrays.fill(result, -1);\n        Stack<Integer> stack = new Stack<>();\n\n        for (int i = 0; i < n; i++) {\n            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {\n                stack.pop();\n            }\n            if (!stack.isEmpty()) {\n                result[i] = nums[stack.peek()];\n            }\n            stack.push(i);\n        }\n\n        return result;\n    }\n}\n\n```\n```java []\n//Next Smaller Element\nimport java.util.Arrays;\nimport java.util.Stack;\n\npublic class NextSmallerElement {\n\n    public static int[] nextSmallerElement(int[] nums) {\n        int n = nums.length;\n        int[] result = new int[n];\n        Arrays.fill(result, -1);\n        Stack<Integer> stack = new Stack<>();\n\n        for (int i = 0; i < n; i++) {\n            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {\n                result[stack.pop()] = nums[i];\n            }\n            stack.push(i);\n        }\n\n        return result;\n    }\n}\n\n```\n```java []\n//Previous Smaller Element\nimport java.util.Arrays;\nimport java.util.Stack;\n\npublic class PreviousSmallerElement {\n\n    public static int[] previousSmallerElement(int[] nums) {\n        int n = nums.length;\n        int[] result = new int[n];\n        Arrays.fill(result, -1);\n        Stack<Integer> stack = new Stack<>();\n\n        for (int i = 0; i < n; i++) {\n            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {\n                stack.pop();\n            }\n            if (!stack.isEmpty()) {\n                result[i] = nums[stack.peek()];\n            }\n            stack.push(i);\n        }\n\n        return result;\n    }\n}\n\n```\n\n## Next Greater Element I\n\n# Code\n```\npublic class Solution {\n    public int[] nextGreaterElement(int[] nums1, int[] nums2) {\n        Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x\n        Stack<Integer> stack = new Stack<>();\n        \n        // Iterate through nums2 and fill the map with next greater elements\n        for (int num : nums2) {\n            while (!stack.isEmpty() && stack.peek() < num) {\n                map.put(stack.pop(), num);\n            }\n            stack.push(num);\n        }   \n        \n        // Update nums1 with the next greater elements found in the map, or -1 if not found\n        for (int i = 0; i < nums1.length; i++) {\n            nums1[i] = map.getOrDefault(nums1[i], -1);\n        }\n        \n        return nums1;\n    }\n}\n\n```\n\n## 84. Largest Rectangle in Histogram\n### Next Smaller Element to right\n\n```java []\n//Next Smaller Element to the right pattern \n\n/*for (int i = 0; i < n; i++) {\n            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {\n                ans[stack.pop()] = arr[i]; //Next Smaller Element to the right pattern \n            }\n            stack.push(i);\n}\n\n*/\nimport java.util.Stack;\n\npublic class Solution {\n\n\n    public int largestRectangleArea(int[] heights) {\n        int maxArea = 0;\n        Stack<Pair> stack = new Stack<>();\n\n        for (int i = 0; i < heights.length; i++) {\n            int start = i;\n            // Pop elements from stack while the current height is less than the height at stack\'s top\n            while (!stack.isEmpty() && stack.peek().height > heights[i]) {\n                Pair pair = stack.pop();\n                int index = pair.index;\n                int height = pair.height;\n                maxArea = Math.max(maxArea, height * (i - index));\n                start = index;  // Update start to the index of the popped element\n            }\n            stack.push(new Pair(start, heights[i]));  // Push current index and height as a pair\n        }\n\n        // Process remaining elements in the stack\n        for (Pair pair : stack) {\n            int index = pair.index;\n            int height = pair.height;\n            maxArea = Math.max(maxArea, height * (heights.length - index));\n        }\n\n        return maxArea;\n    }\n    class Pair {\n        int index;\n        int height;\n\n        Pair(int index, int height) {\n            this.index = index;\n            this.height = height;\n        }\n    }\n}\n```\n## 85. Maximal Rectangle\n\n```java []\nimport java.util.Stack;\n\npublic class Solution {\n    public int maximalRectangle(char[][] matrix) {\n        int n = matrix.length;\n        if (n == 0) return 0;\n        int m = matrix[0].length;\n        if (m == 0) return 0;\n\n        int[][] mat = new int[n][m];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                mat[i][j] = matrix[i][j] == \'1\' ? 1 : 0;\n            }\n        }\n\n        return maximalAreaOfSubMatrixOfAll1(mat, n, m);\n    }\n\n    public int maximalAreaOfSubMatrixOfAll1(int[][] mat, int n, int m) {\n        int maxArea = 0;\n        int[] height = new int[m];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (mat[i][j] == 1) {\n                    height[j]++;\n                } else {\n                    height[j] = 0;\n                }\n            }\n            int area = largestRectangleArea(height);\n            maxArea = Math.max(maxArea, area);\n        }\n        return maxArea;\n    }\n\n        public int largestRectangleArea(int[] heights) {\n        int maxArea = 0;\n        Stack<Pair> stack = new Stack<>();\n\n        for (int i = 0; i < heights.length; i++) {\n            int start = i;\n            // Pop elements from stack while the current height is less than the height at stack\'s top\n            while (!stack.isEmpty() && stack.peek().height > heights[i]) {\n                Pair pair = stack.pop();\n                int index = pair.index;\n                int height = pair.height;\n                maxArea = Math.max(maxArea, height * (i - index));\n                start = index;  // Update start to the index of the popped element\n            }\n            stack.push(new Pair(start, heights[i]));  // Push current index and height as a pair\n        }\n\n        // Process remaining elements in the stack\n        for (Pair pair : stack) {\n            int index = pair.index;\n            int height = pair.height;\n            maxArea = Math.max(maxArea, height * (heights.length - index));\n        }\n\n        return maxArea;\n    }\n    class Pair {\n        int index;\n        int height;\n\n        Pair(int index, int height) {\n            this.index = index;\n            this.height = height;\n        }\n    }\n}\n```\n11. Container With Most Water\n42. Trapping Rain Water(similair)\n2517. Maximum Tastiness of Candy Basket (similair)\n2560. House Robber IV (similair)\n198. House Robber (DP)\n213. House Robber II(DP)\n337. House Robber III (DP)\n[907. Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/solutions/5165808/monotonic-patter-continuation/)\n\nIntroduction To stack and NEG pattern - **4 variations** covered in\n\n[232. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/solutions/5203561/implement-queue-using-stacks/)\n[225. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/solutions/5203563/implement-stacks-using-queue/)\n[155. Min Stack](https://leetcode.com/problems/min-stack/solutions/4185675/java-simple-solution-using-two-stack-and-one-stack/)\n[496. Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/solutions/5164552/must-read-intuitive-pattern-for-deep-understanding-of-nge-and-nsm/) **very very important**\n[503. Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/solutions/5201809/brute-intuitive-solution-beats-98-monotonic-pattern/)\n[907. Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/solutions/5165808/monotonic-patter-continuation/) **pattern**\n[11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/solutions/5165076/must-read-maximum-water-pattern/)\n[42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/solutions/5165626/building-intuitive-solution-one-step-at-a-time/)\n[1856. Maximum Subarray Min-Product](https://leetcode.com/problems/maximum-subarray-min-product/solutions/5167159/must-read-monotonic-stack-pattern-variations/)\n[735. Asteroid Collision](https://leetcode.com/problems/asteroid-collision/solutions/5166334/brute-solution/)\n[402. Remove K Digits](https://leetcode.com/problems/remove-k-digits/solutions/5166502/beast-intuitive-approach-step-by-step-nsg-to-right/)\n[2104. Sum of Subarray Ranges](https://leetcode.com/problems/sum-of-subarray-ranges/solutions/5166891/beastt-solution/)\n[84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/5172029/monotonic-stack-pattern-deep-understanding/)\n[85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/solutions/5201947/brute-intuitive-solution-beats-98-monotonic-stack-pattern-deep-understanding/)\n[739. Daily Temperatures](https://leetcode.com/problems/daily-temperatures/solutions/5167031/must-read-monotonic-stack-pattern-variations/) **Fundamental**\n[853. Car Fleet](https://leetcode.com/problems/car-fleet/solutions/5167204/must-read-monotonic-stack-pattern-variations/)\n[150. Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/solutions/5172161/stack-intuitive-solution/)\n[895. Maximum Frequency Stack](https://leetcode.com/problems/maximum-frequency-stack/solutions/5172171/stack-implementation-problem/) **VVI** Implementation problem\n[173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/solutions/5172179/brute-solution/)\n[682. Baseball Game](https://leetcode.com/problems/baseball-game/solutions/5172183/straight-forward-approach/)\n[1209. Remove All Adjacent Duplicates in String II](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/solutions/5172210/stack-solution-pattern/) **Must Go through**\n[456. 132 Pattern](https://leetcode.com/problems/132-pattern/solutions/5202876/monotonic-stack/)\n[22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/solutions/5202882/monotonic-stack/)\n[460. LFU Cache]()\n[146. LRU Cache]()\n[901. Online Stock Span](https://leetcode.com/problems/online-stock-span/solutions/5172217/stack-nge-and-nse-deep-understanding/) **Must Read**\n[239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/solutions/5175931/nge-pattern/) **All three solution**\n[856. Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/solutions/5203496/scoreofparentheses/)\n[844. Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/solutions/5203544/brute-and-optimized-backspacecompare-beats-100/)\n[71. Simplify Path](https://leetcode.com/problems/simplify-path/solutions/5203538/simplifypath/)\n\n<br/>\n\n\n\n
['Java']