Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Next Greater Element Using a Stack

Understand how to solve the next greater element problem by using a stack to track elements in an array. This lesson demonstrates iterating backward through the array, using a stack to compare and find the next greater value efficiently. Learn to update results dynamically and improve runtime complexity from O(n squared) to O(n) through a practical coding example in C#.

We'll cover the following...

Solution: Stack iteration

C#
using System;
using System.Collections.Generic;
namespace chapter_4
{
    class Challenge_7
    {
        static int [] nextGreaterElement(int [] arr, int size)
        {
            Stack <int>stack = new Stack<int>() ;
            
            int [] result = new int[size];
            int next, top;
            for (int i = size - 1; i >= 0; i--)
            {
                next = arr[i]; //potential nextGreaterElement
                if(stack.Count > 0)
                {
                    top = stack.Peek();
                }
                else
                {
                    top = -1;
                }
                while ((stack.Count != 0) && (top <= next))
                {
                    stack.Pop();
                    if (stack.Count > 0)
                    {
                        top = stack.Peek();
                    }
                    else
                    {
                        top = -1;
                    }
                }
                if (stack.Count != 0)
                    result[i] = stack.Peek();
                else
                    result[i] = -1;
                //For next iteration
                stack.Push(next);
            } //end of for loop
            return result;
        }
        static void Main(string[] args)
        {
            int [] arr = { 4, 6, 3, 2, 8, 1, 9, 9 };
            int arr_size = arr.Length;
            int [] res = nextGreaterElement(arr, arr_size);
            Console.WriteLine("____Result____" );
            for (int i = 0; i < arr_size; i++)
                Console.WriteLine(arr[i] + " ---> " + res[i]);
        }
    }
}

Explanation

Although this method can be solved by brute force using nested loops, a stack can do it much more efficiently.

Using the for-loop on line 17, iterate the array from the last element to the first one; because at ...