Leetcode 503. Next Greater Element II

Problem Explanation

This problem requires you to find the next greater number for every element in a circular array. When you reach the last element of the array, you should continue searching from the beginning of the array.

To provide more context, you're given an array (under the assumption that the next element of the last element is the first element of the array). Your task is to print the 'Next Greater Number' for every element.

The 'Next Greater Number' of a number x is the first number greater than x as you traverse through the array. If there is no number greater than x, you should output -1.

It's important to note that because the array is circular, if you reach the end of the array and you haven't found a greater number, you should continue searching from the beginning of the array.

Let's take an example to demonstrate this:

1Example:
2
3Input: [1,2,1]
4Output: [2,-1,2]
5
6Explanation: The next greater number of the first '1' is 2 as you traverse through the array. But there is no greater number found for '2' hence -1 and for the second '1', the next greater number is again 2 because the array is circular and we can find 2 at the second index.

Problem Approach

This problem can be efficiently solved using a data structure called a stack. A stack is perfect for this problem because it allows us to keep track of the indexes of the numbers that we have seen so far and we haven't found the next greater number for them.

The approach is as follows:

1. Initialize an empty stack and an answers array of the same size as the input array filled with -1.

2. Iterate through the array two times. The reason why we need to go through the array two times is because the array is circular. By scanning it two times, we ensure that each element has the chance to compare itself with all remaining numbers to its right.

3. During each iteration, while stack is not empty and the current number is greater than the number at the index at the top the stack, we update the answers array at that index with the current number. We keep on popping the stack until we find a number which is greater or the stack gets empty.

4. If we are in the first iteration, we push the index to the stack.

The final answers array is the solution to the problem.

Python Solution

1
2python
3    class Solution:
4        def nextGreaterElements(self, nums: List[int]) -> List[int]:
5            n = len(nums)
6            res = [-1] * n
7            stack = []  # store index
8            for i in range(n * 2):
9                while stack and (nums[stack[-1]] < nums[i % n]):
10                    res[stack.pop()] = nums[i % n]
11                if i < n:
12                    stack.append(i)
13            return res

Java Solution

1
2java
3    class Solution {
4        public int[] nextGreaterElements(int[] nums) {
5            int n = nums.length;
6            int[] res = new int[n];
7            Arrays.fill(res, -1);
8            Stack<Integer> stack = new Stack<>();
9            for (int i = 0; i < n * 2; i++) {
10                while (!stack.empty() && nums[stack.peek()] < nums[i % n]) 
11                    res[stack.pop()] = nums[i % n];
12                if (i < n)
13                    stack.push(i);
14            }
15            return res;
16        }
17    }

Javascript Solution

1
2javascript
3    var nextGreaterElements = function(nums) {
4        const n = nums.length;
5        const res = Array(n).fill(-1);
6        const stack = [];
7        for(let i = 0; i < n * 2; i++) {
8            while(stack.length > 0 && nums[stack[stack.length - 1]] < nums[i % n]){
9                res[stack.pop()] = nums[i % n];
10            }
11            if(i < n) stack.push(i);
12        }
13        return res;
14    };

C++ Solution

1
2cpp
3    class Solution {
4    public:
5        vector<int> nextGreaterElements(vector<int>& nums) {
6            int n = nums.size();
7            vector<int> res(n, -1);
8            stack<int> stack;  
9            for (int i = 0; i < n * 2; ++i) {
10                while (!stack.empty() && nums[stack.top()] < nums[i%n]){
11                    res[stack.top()] = nums[i % n];
12                    stack.pop();
13                }
14                if (i < n) stack.push(i);
15            }
16            return res;
17        }
18    };

C# Solution

1
2csharp
3    public class Solution {
4        public int[] NextGreaterElements(int[] nums) {
5            int n = nums.Length;
6            int[] res = new int[n];
7            for(int i = 0; i < n; i++)
8                res[i] = -1;
9            Stack<int> stack = new Stack<int>();
10            for (int i = 0; i < n * 2; i++) {
11                while (stack.Count>0 && nums[stack.Peek()] < nums[i % n]) 
12                    res[stack.Pop()] = nums[i % n];
13                if (i < n)
14                    stack.Push(i);
15            }
16            return res;
17        }
18    }

Each of these solutions achieves the same goal using similar methods, with the differences primarily being in syntax due to the different language requirements.

Python, Java, JavaScript, C++ and C# all use stacks to keep track of the indices of elements. Also, they all initialize result arrays to -1, to default any elements that do not have a greater next number to -1.

Python uses the ‘class’ keyword to construct the function, while Java uses the ‘public’ keyword. JavaScript uses a variable assigned to a function.

The solution in C++ is quite similar to Java and Python. One notable difference is the ‘vector’ data type in C++, which is similar to a list in Python or an array in Java and JavaScript.

The C# solution appears similar to C++, Java, and Python, but has the specificities of C# like usage of the keyword public.

Conclusion

This problem presents a good example for practicing with stacks and arrays. It demonstrates how a seemingly complex problem can be solved elegantly using the correct data structures.

Keep in mind that even languages you are less familiar with often have similar approaches to problem solving. So, even if you usually code in Python or Java, seeing how this problem is solved in JavaScript, C++ or C# can be beneficial in growing your overall programming skills.

In general, the more languages you are exposed to, the more versatile a programmer you can become. The ability to leverage the strengths of specific languages and to implement algorithms in different languages is a valuable skill in computer science and coding. Always make sure to practice problems in different languages when you have the chance.