{
"$type": "site.standard.document",
"bskyPostRef": {
"cid": "bafyreiaqze7bfmlmnwg35klxeamdyzxj2qiokd5qt56tqlwxyp3snw7cou",
"uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mp4ykzwkfmj2"
},
"coverImage": {
"$type": "blob",
"ref": {
"$link": "bafkreihgdt6i43ayqaj4bjvtgvzt7fjrrxvuhhca7ijvk5jk26fy6y5qie"
},
"mimeType": "image/webp",
"size": 54048
},
"path": "/jaspreet_singh_86ae1740ac/next-greater-element-i-monotonic-stack-2km6",
"publishedAt": "2026-06-25T17:24:44.000Z",
"site": "https://dev.to",
"tags": [
"algorithms",
"interview",
"java",
"leetcode",
"leetcode.com"
],
"textContent": "\nleetcode.com\n\n\n## Problem Statement\n\nYou are given two arrays:\n\n * `nums1` is a subset of `nums2`.\n * For every element in `nums1`, find the first greater element to its right in `nums2`.\n\n\n\nIf no greater element exists, return `-1`.\n\n## Brute Force Intuition\n\nIn an interview, you can explain it like this:\n\n> For every element in `nums1`, first locate its position in `nums2`. Then traverse towards the right until a greater element is found.\n\nAlthough simple, this repeatedly scans the same elements.\n\n### Complexity\n\n * Time Complexity: **O(N × M)**\n * Space Complexity: **O(1)**\n\n\n\n### Brute Force Code\n\n\n class Solution {\n\n public int[] nextGreaterElement(int[] nums1, int[] nums2) {\n\n int[] ans = new int[nums1.length];\n\n for (int i = 0; i < nums1.length; i++) {\n\n int index = -1;\n\n // Find element in nums2\n for (int j = 0; j < nums2.length; j++) {\n\n if (nums2[j] == nums1[i]) {\n index = j;\n break;\n }\n }\n\n ans[i] = -1;\n\n // Search towards right\n for (int j = index + 1; j < nums2.length; j++) {\n\n if (nums2[j] > nums1[i]) {\n ans[i] = nums2[j];\n break;\n }\n }\n }\n\n return ans;\n }\n }\n\n\n## Moving Towards the Optimal Approach\n\nNotice that while scanning every element, we repeatedly search the right side.\n\nInstead, can we compute the next greater element for **every element in nums2 only once**?\n\nYes!\n\nWe'll use a **Monotonic Decreasing Stack**.\n\n## Pattern Recognition\n\nWhenever you see:\n\n * Next Greater Element\n * Previous Greater Element\n * Next Smaller Element\n * Previous Smaller Element\n\n\n\nThink:\n\n**Monotonic Stack**\n\n## Key Observation\n\nTraverse `nums2` from **right to left**.\n\nMaintain a stack such that:\n\n\n\n Top of stack\n =\n First Greater Element\n\n\nBefore pushing the current element:\n\nRemove all smaller elements because they'll never become the next greater for future elements.\n\n## Optimal Approach\n\nFor every element:\n\n\n\n Remove all smaller elements.\n\n\nIf stack becomes empty:\n\n\n\n Next Greater = -1\n\n\nElse:\n\n\n\n Next Greater = Stack Top\n\n\nStore this mapping in a HashMap.\n\nFinally, answer each query in `nums1` using the map.\n\n## Optimal Java Solution\n\n\n class Solution {\n\n public int[] nextGreaterElement(int[] nums1, int[] nums2) {\n\n HashMap<Integer, Integer> map = new HashMap<>();\n\n Stack<Integer> st = new Stack<>();\n\n for (int i = nums2.length - 1; i >= 0; i--) {\n\n while (!st.isEmpty() && st.peek() < nums2[i]) {\n st.pop();\n }\n\n if (st.isEmpty()) {\n map.put(nums2[i], -1);\n } else {\n map.put(nums2[i], st.peek());\n }\n\n st.push(nums2[i]);\n }\n\n int[] ans = new int[nums1.length];\n\n for (int i = 0; i < nums1.length; i++) {\n ans[i] = map.get(nums1[i]);\n }\n\n return ans;\n }\n }\n\n\n## Dry Run\n\n### Input\n\n\n nums1 = [2,4]\n\n nums2 = [1,2,3,4]\n\n\nTraverse from right:\n\n### Step 1\n\n\n Current = 4\n\n Stack = []\n\n Next Greater = -1\n\n Push 4\n\n\nStack:\n\n\n\n 4\n\n\n### Step 2\n\n\n Current = 3\n\n Stack Top = 4\n\n Next Greater = 4\n\n Push 3\n\n\nStack:\n\n\n\n 3\n 4\n\n\n### Step 3\n\n\n Current = 2\n\n Stack Top = 3\n\n Next Greater = 3\n\n Push 2\n\n\nStack:\n\n\n\n 2\n 3\n 4\n\n\n### Step 4\n\n\n Current = 1\n\n Stack Top = 2\n\n Next Greater = 2\n\n\nHashMap becomes:\n\n\n\n 1 → 2\n\n 2 → 3\n\n 3 → 4\n\n 4 → -1\n\n\nAnswer:\n\n\n\n 2 → 3\n\n 4 → -1\n\n\nResult:\n\n\n\n [3, -1]\n\n\n## Why Monotonic Stack Works?\n\nEvery element enters the stack once.\n\nEvery element leaves the stack once.\n\nThe stack always maintains elements in decreasing order.\n\nHence:\n\n\n\n Top of stack\n =\n Nearest Greater Element\n\n\nwithout repeatedly scanning the array.\n\n## Complexity Analysis\n\nMetric | Complexity\n---|---\nTime Complexity | O(N + M)\nSpace Complexity | O(N)\n\nWhere:\n\n * `N = nums2.length`\n * `M = nums1.length`\n\n\n\n## Interview One-Liner\n\n> Traverse from right to left using a monotonic decreasing stack to precompute the next greater element for every value, then answer queries in O(1) using a HashMap.\n\n## Pattern Learned\n\n\n Next Greater Element\n +\n Nearest Greater\n +\n Right Side Query\n\n => Monotonic Decreasing Stack\n\n\n### Similar Problems\n\n * Next Greater Element I\n * Next Greater Element II\n * Daily Temperatures\n * Stock Span Problem\n * Next Smaller Element\n * Previous Greater Element\n\n\n\n## Memory Trick\n\nThink:\n\n\n\n Current Element\n ↓\n Remove Smaller Elements\n ↓\n Stack Empty ?\n ↓\n Yes → -1\n\n No → Stack Top\n\n\n### Mental Model\n\n\n Need Nearest Greater on Right\n\n ↓\n\n Traverse Right to Left\n\n ↓\n\n Maintain Decreasing Stack\n\n ↓\n\n Top = Answer\n\n\nWhenever you hear:\n\n> \"Find the next greater element\"\n\nyour brain should immediately think:\n\n**Monotonic Stack**",
"title": "Next Greater Element I | Monotonic Stack"
}