## C# || How To Find The Next Greater Element In An Array Using C#

The following is a module with functions which demonstrates how to find the next greater element in an array using C#.

1. Next Greater – Problem Statement

The **next greater element** of some element **x** in an array is the **first greater** element that is **to the right** of **x** in the same array.

You are given two **distinct 0-indexed** integer arrays **nums1** and **nums2**, where **nums1** is a subset of **nums2**.

For each **0 <= i < nums1.length**, find the index **j** such that **nums1[i] == nums2[j]** and determine the **next greater element** of **nums2[j]** in **nums2**. If there is no next greater element, then the answer for this query is **-1**.

Return an array **ans** of length **nums1.length** such that **ans[i]** is the **next greater element** as described above.

**Example 1:**

Input:nums1 = [4,1,2], nums2 = [1,3,4,2]

Output:[-1,3,-1]

Explanation:The next greater element for each value of nums1 is as follows:

- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.

- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

**Example 2:**

Input:nums1 = [2,4], nums2 = [1,2,3,4]

Output:[3,-1]

Explanation:The next greater element for each value of nums1 is as follows:

- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.

- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

2. Next Greater – Solution

The following is a solution which demonstrates how to find the next greater element in an array.

This solution uses the monotonic stack approach. This solution finds the next greater element for each array value in the second array, and uses that to find the next greater element for each matching value in the first array.

To determine the next greatest element, a stack is used to keep track of the items we’ve already seen. The array index of the item is saved to the stack.

For each loop iteration, the item at the top of the stack is checked to see if it is less than the current array item being checked. If the item at the top of the stack is less than the current array item, then the current array item is saved to the result index that matches the value from the top of the stack.

Once the next greatest elements have been found from nums2, that information is used to populate the final result from the matching values found in nums1

```
```
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
// ============================================================================// Author: Kenneth Perkins// Date: Oct 14, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the next greater element in an array// ============================================================================public class Solution { public int[] NextGreaterElement(int[] nums1, int[] nums2) { // For each element in nums2, get the next greatest element var nums2NextGreatest = GetNextGreatest(nums2); // Create a dictionary with the next greatest of each element from nums2 var seen = new Dictionary<int, int>(); for (int index = 0; index < nums2.Length; ++index) { seen[nums2[index]] = nums2NextGreatest[index]; } // From the items in the dictionary, populate the results var result = new int[nums1.Length]; for (int index = 0; index < nums1.Length; ++index) { result[index] = seen[nums1[index]]; } return result; } public int[] GetNextGreatest(int[] nums) { // Create a stack that keeps track of the item and its index var stack = new Stack<int>(); var result = new int[nums.Length]; // Go through array and find the next greatest value for (int index = 0; index < nums.Length; ++index) { // Default the value at index to -1 result[index] = -1; // Check to see if the item at the top of the stack is less than current item while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) { // Save the current item at the result index result[stack.Peek()] = nums[index]; stack.Pop(); } // Save array index to the stack stack.Push(index); } return result; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[-1,3,-1]

[3,-1]

## Leave a Reply