October 14, 2021 – My Programming Notes

Daily Archives: October 14, 2021

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

October 14, 2021 admin No comments

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





		
		
			2. Next Greater - Solution
			
C#
			
			// ============================================================================
//    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/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
				
						// ============================================================================
//    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]

Daily Archives: October 14, 2021

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

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories