Given an array of integers, find the next greater element for every element in the array. The next greater element of a number x is the first greater number to the right of x in the array.
In other words, for each element A[i] in the array, find an element A[j] such that j > i and A[j] > A[i] and the value of j should be as minimum as possible. If the next greater element doesn’t exist in the array for any element, consider it -1.
For example,
The idea is to use two nested loops. The outer loop takes each element of the array from left to right. The inner loop considers all elements to the “right” of the element picked by the outer loop. Terminate the inner loop as soon as the first larger element is found, which would be the next greater element for the element picked by the outer loop.
The time complexity of this approach is O(n2). Below is the implementation in C, Java, and Python based on the above idea.
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
|
#include <stdio.h>
// Find the next greater element for every element in the array
void findNextGreaterElements(int arr[], int n)
{
// do for each element
for (int i = 0; i < n; i++)
{
// keep track of the next greater element for element `arr[i]`
int next = –1;
// process elements on the right of element `arr[i]`
for (int j = i + 1; j < n; j++)
{
// break the inner loop at the first larger element on the
// right of element `arr[i]`
if (arr[j] > arr[i])
{
next = arr[j];
break;
}
}
printf(“%d “, next);
}
}
int main(void)
{
int arr[] = { 2, 7, 3, 5, 4, 6, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
findNextGreaterElements(arr, n);
return 0;
}
|
Output:
7 8 5 6 6 8 -1
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
|
class Main {
// Find the next greater element for every element in the array
public static void findNextGreaterElements(int[] arr)
{
// do for each element
for (int i = 0; i < arr.length; i++)
{
// keep track of the next greater element for element `arr[i]`
int next = –1;
// process elements on the right of element `arr[i]`
for (int j = i + 1; j < arr.length; j++)
{
// break the inner loop at the first larger element on the
// right of element `arr[i]`
if (arr[j] > arr[i])
{
next = arr[j];
break;
}
}
System.out.print(next + ” “);
}
}
public static void main(String[] args)
{
int[] arr = { 2, 7, 3, 5, 4, 6, 8 };
findNextGreaterElements(arr);
}
}
|
Output:
7 8 5 6 6 8 -1
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# Find the next greater element for every element in the array
def findNextGreaterElements(arr):
# do for each element
for i in range(len(arr)):
# keep track of the next greater element for element `arr[i]`
next = –1
# process elements on the right of element `arr[i]`
for j in range(i + 1, len(arr)):
# break the inner loop at the first larger element on the
# right of element `arr[i]`
if arr[j] > arr[i]:
next = arr[j]
break
print(next, end=‘ ‘)
if __name__ == ‘__main__’:
arr = [2, 7, 3, 5, 4, 6, 8]
findNextGreaterElements(arr)
|
Output:
7 8 5 6 6 8 -1
Download Run Code
Output:
7 8 5 6 6 8 -1
Download Run Code
Output:
7 8 5 6 6 8 -1
Download Run Code
Output:
7 8 5 6 6 8 -1
The time complexity can be easily reduced to linear by using extra space. The idea is to use a stack data structure.
Following is the C++, Java, and Python program that demonstrates this algorithm. Note that we’re pushing indexes into the stack instead of the actual elements. Now the next greater element can be set for the popped elements using their index.
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
43
44
45
46
|
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// Find the next greater element for every element in the array
vector<int> findNextGreaterElements(const vector<int> &arr)
{
int n = arr.size();
vector<int> result(n, –1);
// create an empty stack
stack<int> s;
// do for each element
for (int i = 0; i < n; i++)
{
// loop till we have a greater element on top or stack becomes empty
// Keep popping elements from the stack that are smaller than the current
// element, and set their next greater element to the current element
while (!s.empty() && arr[s.top()] < arr[i])
{
result[s.top()] = arr[i];
s.pop();
}
// push current “index” to stack
s.push(i);
}
return result;
}
int main()
{
vector<int> arr = { 2, 7, 3, 5, 4, 6, 8 };
vector<int> result = findNextGreaterElements(arr);
for (int i: result) {
cout << i << ‘ ‘;
}
return 0;
}
|
Output:
7 8 5 6 6 8 -1
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
|
import java.util.Arrays;
import java.util.Stack;
class Main {
// Find the next greater element for every element in the array
public static int[] findNextGreaterElements(int[] arr)
{
int[] result = new int[arr.length];
Arrays.fill(result, –1);
// create an empty stack
Stack<Integer> s = new Stack<>();
// do for each element
for (int i = 0; i < arr.length; i++)
{
// loop till we have a greater element on top or stack becomes empty
// Keep popping elements from the stack that are smaller than the current
// element, and set their next greater element to the current element
while (!s.isEmpty() && arr[s.peek()] < arr[i]) {
result[s.pop()] = arr[i];
}
// push current “index” to stack
s.push(i);
}
return result;
}
public static void main(String[] args)
{
int[] arr = { 2, 7, 3, 5, 4, 6, 8 };
int[] result = findNextGreaterElements(arr);
System.out.println(Arrays.toString(result));
}
}
|
Output:
[7, 8, 5, 6, 6, 8, -1]
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
31
|
from collections import deque
# Find the next greater element for every element in the array
def findNextGreaterElements(arr):
result = [–1] * len(arr)
# create an empty stack
s = deque()
# do for each element
for i in range(len(arr)):
# loop till we have a greater element on top or stack becomes empty
# Keep popping elements from the stack that are smaller than the current
# element, and set their next greater element to the current element
while s and arr[s[–1]] < arr[i]:
result[s[–1]] = arr[i]
s.pop()
# push current “index” to stack
s.append(i)
return result
if __name__ == ‘__main__’:
arr = [2, 7, 3, 5, 4, 6, 8]
print(findNextGreaterElements(arr))
|
Output:
[7, 8, 5, 6, 6, 8, -1]
Download Run Code
Output:
7 8 5 6 6 8 -1
Download Run Code
Output:
[7, 8, 5, 6, 6, 8, -1]
Download Run Code
Output:
[7, 8, 5, 6, 6, 8, -1]
Here’s another stack-based solution where elements are processed from right to left in the array.
Following is the C++, Java, and Python program that demonstrates this algorithm.
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
43
44
45
46
47
48
|
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> findNextGreaterElements(const vector<int> &arr)
{
int n = arr.size();
vector<int> result(n, –1);
// create an empty stack
stack<int> s;
// process each element from right to left
for (int i = n – 1; i >= 0; i—)
{
// loop till we have a greater element on top or stack becomes empty
while (!s.empty())
{
// pop elements that aren’t greater than the current element
if (s.top() <= arr[i]) {
s.pop();
}
// the next greater element is now on the top of the stack
else {
result[i] = s.top();
break;
}
}
// push current element to stack
s.push(arr[i]);
}
return result;
}
int main()
{
vector<int> arr = { 2, 7, 3, 5, 4, 6, 8 };
vector<int> result = findNextGreaterElements(arr);
for (int i: result) {
cout << i << ‘ ‘;
}
return 0;
}
|
Output:
7 8 5 6 6 8 -1
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
46
|
import java.util.Arrays;
import java.util.Stack;
class Main
{
public static int[] findNextGreaterElements(int[] arr)
{
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, –1);
// create an empty stack
Stack<Integer> s = new Stack<>();
// process each element from right to left
for (int i = n – 1; i >= 0; i—)
{
// loop till we have a greater element on top or stack becomes empty
while (!s.empty())
{
// pop elements that aren’t greater than the current element
if (s.peek() <= arr[i]) {
s.pop();
}
// the next greater element is now on the top of the stack
else {
result[i] = s.peek();
break;
}
}
// push current element to stack
s.push(arr[i]);
}
return result;
}
public static void main(String[] args)
{
int[] arr = { 2, 7, 3, 5, 4, 6, 8 };
int[] result = findNextGreaterElements(arr);
System.out.println(Arrays.toString(result));
}
}
|
Output:
[7, 8, 5, 6, 6, 8, -1]
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
31
32
|
from collections import deque
def findNextGreaterElements(arr):
n = len(arr)
result = [–1] * n
# create an empty stack
s = deque()
# process each element from right to left
for i in reversed(range(n)):
# loop till we have a greater element on top or stack becomes empty
while s:
# pop elements that aren’t greater than the current element
if s[–1] <= arr[i]:
s.pop()
# the next greater element is now on the top of the stack
else:
result[i] = s[–1]
break
# push current element to stack
s.append(arr[i])
return result
if __name__ == ‘__main__’:
arr = [2, 7, 3, 5, 4, 6, 8]
result = findNextGreaterElements(arr)
print(result)
|
Output:
[7, 8, 5, 6, 6, 8, -1]
Download Run Code
Output:
7 8 5 6 6 8 -1
Download Run Code
Output:
[7, 8, 5, 6, 6, 8, -1]
Download Run Code
Output:
[7, 8, 5, 6, 6, 8, -1]
The time complexity of both stack-based solutions is O(n) since every element is pushed and popped at most once to the stack. The auxiliary space used is O(n) for the stack.
Exercise: Extend the solution for a circular array to search circularly to find the next greater element.