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

October 15, 2021 admin No comments

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

1. Circular Next Greater – Problem Statement

Given a circular integer array nums (i.e., the next element of nums[nums.length – 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Example 1:

Input: nums = [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number. The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

Input: nums = [1,2,3,4,3] Output: [2,3,4,-1,4]

2. Circular Next Greater – Solution

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

This solution uses the monotonic stack approach. This solution finds the next greater element for each array value, in the first pass, and then uses a second pass to process any remaining values since the array is circular.





		
		
			2. Circular Next Greater - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 15, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the next greater element in a 
//        circular array
// ============================================================================
public class Solution {
    public int[] NextGreaterElements(int[] nums) {
        var result = GetNextGreatest(nums);
        return result;
    }

    public int[] GetNextGreatest(int[] nums) {
        var result = new int[nums.Length];
        var stack = new Stack<int>();

        for (int index = 0; index < nums.Length; ++index) {
            // Default to -1 for this index
            result[index] = -1;

            // Fill in values that have a greater element
            while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) {
                result[stack.Peek()] = nums[index];
                stack.Pop();
            }

            // Add index to stack
            stack.Push(index);
        }

        // Fill in any left over values since this is circular
        for (int index = 0; index < nums.Length && stack.Count > 0; ++index) {
            while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) {
                result[stack.Peek()] = nums[index];
                stack.Pop();
            }
        }

        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 15, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the next greater element in a 
//        circular array
// ============================================================================
public class Solution {
    public int[] NextGreaterElements(int[] nums) {
        var result = GetNextGreatest(nums);
        return result;
    }
 
    public int[] GetNextGreatest(int[] nums) {
        var result = new int[nums.Length];
        var stack = new Stack<int>();
 
        for (int index = 0; index < nums.Length; ++index) {
            // Default to -1 for this index
            result[index] = -1;
 
            // Fill in values that have a greater element
            while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) {
                result[stack.Peek()] = nums[index];
                stack.Pop();
            }
 
            // Add index to stack
            stack.Push(index);
        }
 
        // Fill in any left over values since this is circular
        for (int index = 0; index < nums.Length && stack.Count > 0; ++index) {
            while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) {
                result[stack.Peek()] = nums[index];
                stack.Pop();
            }
        }
 
        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:

[2,-1,2] [2,3,4,-1,4]

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: c-sharp, leetcode, monotonic stack

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

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories