C# Coding Test Course, Finding the Next Greater Number

Problem Description

The Next Greater Element problem involves finding, for each element in an array, the nearest element to its right that is greater than itself.
For each element in the given array, if there exists an element to its right that is greater, it returns that element; otherwise, it returns -1.

Example

For example, if the array is [3, 5, 2, 7]:

  • The next greater element for 3 is 5.
  • The next greater element for 5 is 7.
  • The next greater element for 2 is 7.
  • There is no next greater element for 7. Therefore, it is -1.

Thus, the result is [5, 7, 7, -1].

Approach to the Problem

To solve this problem, an efficient algorithm is required. Using a simple double loop would result in a time complexity of O(n^2), which is inefficient.
By using a stack, this can be processed in O(n).

Reason for Using a Stack

A stack operates under a LIFO (Last In First Out) structure, where the most recently added data is removed first.
By using this, if the current element is greater than the top element of the stack, we can find each element’s next greater element while popping from the stack.
The algorithm using the stack works as follows:

Algorithm Steps

  1. Initialize an array to store the results.
  2. Initialize an empty stack.
  3. Iterate through the elements from left to right.
  4. If the stack is not empty and the current element is greater than the top element of the stack, pop from the stack and set the next greater element for that element to the current element.
  5. Add the index of the current element to the stack.

Code Implementation

Now let’s implement the algorithm described above in C#. Below is the complete code: 

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int[] arr = { 3, 5, 2, 7 };
        int[] result = FindNextGreater(arr);
        Console.WriteLine(string.Join(", ", result)); // Output: 5, 7, 7, -1
    }

    static int[] FindNextGreater(int[] arr)
    {
        int n = arr.Length;
        int[] result = new int[n];
        Stack stack = new Stack();

        for (int i = 0; i < n; i++)
        {
            while (stack.Count > 0 && arr[stack.Peek()] < arr[i])
            {
                result[stack.Pop()] = arr[i];
            }
            stack.Push(i);
        }

        while (stack.Count > 0)
        {
            result[stack.Pop()] = -1;
        }

        return result;
    }
}

Code Explanation

Let’s take a closer look at each part of the code.

  • Variable Initialization: Store the length of the given input array arr in n, and initialize the result array and stack.
  • Main Loop: While iterating through the elements, if the elements indexed in the stack are smaller than the current element, set the current element in the result array and remove that index from the stack.
  • Stack Update: Add the index of the current element to the stack.
  • Process Remaining Stack: Indexes remaining in the stack have no greater element to the right, so set them all to -1.

Conclusion

The problem of finding the next greater element is a good example of how it can be efficiently solved using a stack.
When encountering such problems in coding tests, make sure to actively utilize data structures like stacks or queues.
It’s important to get familiar with various problems through practice.

Additional Practice Problems

  • Try to solve a problem that finds the next greater element for all elements to the left.
  • Explore ways to calculate the next greater element for different data types (e.g., floating-point arrays, etc.).

References

GeeksforGeeks – Next Greater Element
Programiz – C# Arrays

Final Thoughts

Algorithm problems may seem difficult at first, but with repetitive learning and practice, you can become more familiar with them.
I hope you thoroughly understand how to find the next greater element through this course. Try solving various problems, and develop your own coding style.