LeetCode - Next Greater Element II
https://leetcode.com/problems/next-greater-element-ii/
Problems:
Given a circular array (the next element of the last element is the first element of the array), for each position, find the nearest element on the right that is greater.
Solution:
Simplify this problem a bit, given a normal array, find the nearest greater element on the right of each element on the given array.
A = 2 4 1 2 3
R = 4 -1 2 3 -1
The solution is using a stack that maintains a decreasing sequence (top of stack is the smallest number).
At index i, we will try to pop all smaller number on stack, the top after this process is the number that larger than number at index i.
You may ask why is this number the nearest on the right? It’s because of the behavior of stack (LIFO last in first out). The recent popped element on the stack is the recent added element. Then the first number in stack that larger than number at index i is the nearest number.
*My trick: Normally when i face the “circular array”, i will double this array (i.e 1 2 3 → 1 2 3 1 2 3) then try to find a solution around this.*
The same trick will apply to this problem. We will double the input array, traverse from right to left and maintain a stack (behavior as we discussed above). The result is the first half of result array.
Why double array can solve problem? Since we build the stack from right to left, at the index N (length of input array), we already build a stack from index 1 → index N (the last half of array). So we can find the nearest greater of N-th element.
1 | func nextGreaterElements(nums []int) []int { |
Some discussions: Of course there is a solution using modulo instead of double the array. But the trade-off is this will make code harder to read. In this problem, i prefer clean code.
Time complexity O(N) since each we traverse through 2N number and maximum number in stack is 2N.
Memory complexity is O(N)
Support me via: https://ko-fi.com/iamquang95