Find the next greater element for every element in a circular array
Given a circular integer array, find the next greater element for every element in it. The next greater element of an element x in the array is the first larger number to the next of x.
In a circular array, the indices will wrap around as if it were connected end-to-end. In other words, the end of the array wraps around to the start of the array. Therefore, we can search circularly to find the next greater number. If the next greater element doesn’t exist, consider it to be -1.
For example,
Output: [5, -1, 4, 5]
Input: [7, 5, 3, 4]
Output: [-1, 7, 4, 7]
Related Post:
In the above post, we have discussed finding the next greater element for every element in a “normal” array. We can easily extend the solution for “circular” arrays as well, just by looping twice. We can do this by doubling the loop counter and taking the modulo of loop counter indices with n.
The core idea remains the same – for each element x, pop elements that are smaller than x, and set their next greater element to x. This is demonstrated below in C++, Java, and Python:
C++
|
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 |
#include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; vector<int> findNextGreater(vector<int> const &input) { int n = input.size(); vector<int> out(n, -1); stack<int> s; for (int i = 0; i < 2*n; i++) { while (!s.empty() && input[s.top()] < input[i % n]) { out[s.top()] = input[i % n]; s.pop(); } s.push(i % n); } return out; } int main() { vector<int> input = { 3, 5, 2, 4 }; vector<int> out = findNextGreater(input); for_each(out.begin(), out.end(), [](int &i) { cout << i << " "; }); return 0; } |
Output:
5 -1 4 5
Java
|
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 |
import java.util.Arrays; import java.util.Stack; class Main { public static int[] findNextGreater(int[] input) { // base case if (input == null) { return input; } int n = input.length; int[] out = new int[n]; Arrays.fill(out, -1); Stack<Integer> s = new Stack<>(); for (int i = 0; i < 2*n; i++) { while (!s.isEmpty() && input[s.peek()] < input[i % n]) { out[s.pop()] = input[i % n]; } s.add(i % n); } return out; } public static void main(String[] args) { int[] input = { 3, 5, 2, 4 }; int[] out = findNextGreater(input); System.out.println(Arrays.toString(out)); } } |
Output:
[5, -1, 4, 5]
Python
|
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 |
from collections import deque def findNextGreater(input): # base case if not input: return [] n = len(input) out = [-1] * n s = deque() for i in range(2*n): while s and input[s[-1]] < input[i % n]: out[s.pop()] = input[i % n] s.append(i % n) return out if __name__ == '__main__': input = [3, 5, 2, 4] print(findNextGreater(input)) |
Output:
[5, -1, 4, 5]
Note that each element is pushed and popped at most once. Therefore, the time complexity of the above solution is O(n), where n is the input size and requires O(n) extra space for the stack.
We can also process array elements from right to left. The idea is for each element x, loop till we have a greater element on top of the stack or the stack gets empty. When the stack gets a greater element on top, set it as the next greater element of x. This is demonstrated below in C++, Java, and Python:
C++
|
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 |
#include <iostream> #include <stack> #include <vector> #include <algorithm> using namespace std; vector<int> findNextGreater(vector<int> const &input) { int n = input.size(); vector<int> out(n, -1); stack<int> s; for (int i = 2*n - 1; i >= 0; i--) { while (!s.empty()) { if (s.top() <= input[i % n]) { s.pop(); } else { out[i % n] = s.top(); break; } } s.push(input[i % n]); } return out; } int main() { vector<int> input = { 3, 5, 2, 4 }; vector<int> out = findNextGreater(input); for_each(out.begin(), out.end(), [](int &i) { cout << i << " "; }); return 0; } |
Output:
5 -1 4 5
Java
|
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 |
import java.util.Arrays; import java.util.Stack; class Main { public static int[] findNextGreater(int[] input) { // base case if (input == null) { return input; } int n = input.length; int[] out = new int[n]; Arrays.fill(out, -1); Stack<Integer> s = new Stack<>(); for (int i = 2*n - 1; i >= 0; i--) { while (!s.isEmpty()) { if (s.peek() <= input[i % n]) { s.pop(); } else { out[i % n] = s.peek(); break; } } s.add(input[i % n]); } return out; } public static void main(String[] args) { int[] input = { 3, 5, 2, 4 }; int[] out = findNextGreater(input); System.out.println(Arrays.toString(out)); } } |
Output:
[5, -1, 4, 5]
Python
|
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 |
from collections import deque def findNextGreater(input): # base case if not input: return n = len(input) out = [-1] * n s = deque() for i in reversed(range(2*n)): while s: if s[-1] <= input[i % n]: s.pop() else: out[i % n] = s[-1] break s.append(input[i % n]) return out if __name__ == '__main__': input = [3, 5, 2, 4] print(findNextGreater(input)) |
Output:
[5, -1, 4, 5]
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)