{"id":860,"date":"2025-08-11T11:47:46","date_gmt":"2025-08-11T06:17:46","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=860"},"modified":"2025-08-11T11:47:47","modified_gmt":"2025-08-11T06:17:47","slug":"next-larger-element","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/next-larger-element\/","title":{"rendered":"Next Greater Element | Optimal Solution using Stack"},"content":{"rendered":"\n<p>Given an array&nbsp;<strong>arr[ ]<\/strong>&nbsp;of integers, the task is to find the next greater element for each element of the array in order of their appearance in the array. Next greater element of an element in the array is the nearest element on the right which is greater than the current element.<br>If there does not exist next greater of current element, then next greater element for current element is -1. For example, next greater of the last element is always -1.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/next-larger-element-1587115620\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Examples<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [1, 3, 2, 4]<br><strong>Output<\/strong>: [3, 4, 4, -1]<br><strong>Explanation<\/strong>: The next larger element to 1 is 3, 3 is 4, 2 is 4 and for 4, since it doesn't exist, it is -1.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [6, 8, 0, 1, 3]\n<strong>Output<\/strong>: [8, -1, 1, 3, -1]\n<strong>Explanation<\/strong>: The next larger element to 6 is 8, for 8 there is no larger elements hence it is -1, for 0 it is 1 , for 1 it is 3 and then for 3 there is no larger element on right and hence -1.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [10, 20, 30, 50]\n<strong>Output<\/strong>: [20, 30, 50, -1]\n<strong>Explanation<\/strong>: For a sorted array, the next element is next greater element also except for the last element.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [50, 40, 30, 10]\n<strong>Output<\/strong>: [-1, -1, -1, -1]\n<strong>Explanation<\/strong>: There is no greater element for any of the elements in the array, so all are -1.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><br>1 \u2264 arr.size() \u2264 10<sup>6<\/sup><br>0 \u2264 arr[i] \u2264 10<sup>9<\/sup><\/p>\n\n\n<div class=\"wp-block-ub-table-of-contents-block ub_table-of-contents\" id=\"ub_table-of-contents-b79ceda8-c1ed-48c6-9e68-3dd070e94bdf\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"false\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"true\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column \">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#0-brute-force-approach-naive-nested-loops\" style=\"\">Brute Force Approach (Naive Nested Loops)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#7-simplified\" style=\"\">Simplified<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#8-optimal-approach-monotonic-stack\" style=\"\">Optimal Approach (Monotonic Stack)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#15-simplified\" style=\"\">Simplified<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#16-summary-table\" style=\"\">Summary Table<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/#17-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-brute-force-approach-naive-nested-loops\">Brute Force Approach (Naive Nested Loops)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Check every pair: for each element, scan to its right and return the first larger number. If nothing found, use -1. This is how most beginners start and helps cement the purpose of the problem.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For each position i (from 0 to n-1):\n<ul class=\"wp-block-list\">\n<li>Loop from j = i+1 to n-1<\/li>\n\n\n\n<li>If arr[j] > arr[i], set ans[i] = arr[j] and break<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>If inner loop finds no such j, ans[i] remains -1.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def nextLargerElement(self, arr):\n        n = len(arr)\n        ans = [-1] * n    # Initialize all answers as -1\n        for i in range(0, n):\n            # Check for greater element towards right of arr[i]\n            for j in range(i + 1, n):\n                if arr[j] &gt; arr[i]:\n                    ans[i] = arr[j]   # Set the NGE for arr[i]\n                    break   # Stop at the first greater element\n        return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">nextLargerElement<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(arr)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = [-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] * n    <\/span><span style=\"color: #6A9955\"># Initialize all answers as -1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Check for greater element towards right of arr[i]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> arr[j] &gt; arr[i]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    ans[i] = arr[j]   <\/span><span style=\"color: #6A9955\"># Set the NGE for arr[i]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">break<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #6A9955\"># Stop at the first greater element<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Simple double loop; the outer loop is for each element, the inner for searching the next greater.<\/li>\n\n\n\n<li>If a next greater is found, update the answer and move to the next element.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>arr = [4, 5,5]<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For 4: Next greater is 5<\/li>\n\n\n\n<li>For 5: Next greater is 25<\/li>\n\n\n\n<li>For 2: Next greater is 25<\/li>\n\n\n\n<li>For 25: No greater; -1<\/li>\n<\/ul>\n\n\n\n<p>Result: [5, 25, 25, -1]<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>\u00a0O(n\u00b2) &#8211; the outer loop runs n times, and the inner up to n times per iteration.<a href=\"https:\/\/www.geeksforgeeks.org\/dsa\/next-greater-element\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n\n\n\n<li><strong>Space:<\/strong>\u00a0O(n) &#8211; for the result array.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplified\">Simplified<\/h3>\n\n\n\n<p>The intuition is clear, but the approach is inefficient for large arrays due to repeated scanning.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-optimal-approach-monotonic-stack\">Optimal Approach (Monotonic Stack)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Process elements&nbsp;<strong>from right to left<\/strong>&nbsp;(since we&#8217;re looking for the&nbsp;<em>first<\/em>&nbsp;greater on the right). Use a stack to keep &#8220;potential&#8221; NGEs: for each element, pop all smaller or equal values from the stack; for the first bigger value (if the stack is not empty), that&#8217;s the NGE!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initialize stack and result array (all -1s).<\/li>\n\n\n\n<li>Traverse array backward (right to left):\n<ul class=\"wp-block-list\">\n<li>While stack is not empty and stack top &lt;= arr[i], pop stack.<\/li>\n\n\n\n<li>If stack not empty, result[i] = stack[-1]<\/li>\n\n\n\n<li>Push arr[i] onto stack<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def nextLargerElement(self, arr):\n        n = len(arr)\n        result = [-1] * n    # Initialize all answers as -1\n        stack = []           # Stack to store potential NGEs\n        \n        for i in range(n - 1, -1, -1):\n            # Remove elements not greater than arr[i]\n            while len(stack) != 0 and stack[-1] &lt;= arr[i]:\n                stack.pop()\n                \n            # If stack is not empty, assign top as NGE\n            if len(stack) != 0:\n                result[i] = stack[-1]\n            # Push current element to stack for future comparisons\n            stack.append(arr[i])\n        return result\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">nextLargerElement<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(arr)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = [-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] * n    <\/span><span style=\"color: #6A9955\"># Initialize all answers as -1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        stack = []           <\/span><span style=\"color: #6A9955\"># Stack to store potential NGEs<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Remove elements not greater than arr[i]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(stack) != <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> stack[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] &lt;= arr[i]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                stack.pop()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># If stack is not empty, assign top as NGE<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(stack) != <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                result[i] = stack[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Push current element to stack for future comparisons<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            stack.append(arr[i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> result<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>By going right to left, we always maintain the stack as &#8220;decreasing&#8221; from top to bottom.<\/li>\n\n\n\n<li>For every element, we efficiently find its NGE or confirm it&#8217;s -1.<\/li>\n\n\n\n<li>Each element is pushed and popped at most once, thanks to the stack.<a href=\"https:\/\/www.geeksforgeeks.org\/dsa\/next-greater-element\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>arr = [4,5]<a rel=\"noreferrer noopener\" target=\"_blank\" href=\"https:\/\/www.geeksforgeeks.org\/dsa\/next-greater-element\/\"><\/a><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Start at 25, push to stack, NGE = -1<\/li>\n\n\n\n<li>For 2, stack top is 25 > 2, so NGE = 25; push 2<\/li>\n\n\n\n<li>For 5, pop 2 because 2 &lt; 5, now top is 25, NGE = 25<\/li>\n\n\n\n<li>For 4, stack top is 5 > 4, so NGE = 5<\/li>\n<\/ul>\n\n\n\n<p>Results: [5, 25, 25, -1]<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>\u00a0O(n) &#8211; each element is pushed and popped at most once, making it linear in total.<a href=\"https:\/\/www.geeksforgeeks.org\/dsa\/next-greater-element\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n\n\n\n<li><strong>Space:<\/strong>\u00a0O(n) &#8211; used for the stack and result array.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplified\">Simplified<\/h3>\n\n\n\n<p>A classic use of the stack for array problems; fast, elegant, and crucial for interviews!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-summary-table\">Summary Table<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force<\/td><td>O(n\u00b2)<\/td><td>O(n)<\/td><td>Learning\/dry run<\/td><\/tr><tr><td>Stack-Based<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Interviews\/all n<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"17-conclusion\">Conclusion<\/h2>\n\n\n\n<p>The&nbsp;<strong>Next Greater Element<\/strong>&nbsp;problem is a canonical example of how stacks can convert quadratic brute force into linear time. Always start with brute force for intuition, but be sure to master the stack-based approach for efficient, scalable solutions in coding interviews!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an array&nbsp;arr[ ]&nbsp;of integers, the task is to find the next greater element for each element of the array in order of their appearance in the array. Next greater element of an element in the array is the nearest element on the right which is greater than the current element.If there does not exist<\/p>\n","protected":false},"author":1,"featured_media":862,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,4],"tags":[8,37],"class_list":{"0":"post-860","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-easy","10":"tag-stack-and-queues"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/next-greater-element-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/860","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=860"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/860\/revisions"}],"predecessor-version":[{"id":863,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/860\/revisions\/863"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/862"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=860"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=860"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=860"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}