Coding rounds in the interviews of IT companies check a candidateâ€™s ability to develop an efficient and less complex solution to problems. So to ace that round, we must be well versed with common questions and their best answers.

Here the first element larger than 2 on its right side is 7, while there is no next smaller element after 2, so our output will be -1.

The second part of our questions says, â€śfor every element in an arrayâ€ť, so we have to find the largest and smallest elements after each element.

Let us consider the same array shown above and find the next greater and smaller element for every element.

For 7,

Next greater element = 8 and next smaller element = 3

For 3,

Next greater element = 5 and next smaller element = -1

For 5,

Next greater element = 6 and next smaller element = 4

For 4,

Next greater element = 6 and next smaller element = -1

For 6,

Next greater element = 8 and next smaller element = -1

For the last element, here 8, both the next greater and smaller elements will always be -1 since there is no element after it.

Thus, the final array with the next greater elements is:

Similarly, the final array with the next smaller elements is as follows:

Now that weâ€™re clear with the problem we have to solve, let us see how we solve it.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Method 1: Brute force

The simplest solution which comes to our mind is usually the brute force solution. Most of the time, this solution isnâ€™t efficient with respect to the time and space complexity, so it isnâ€™t preferred.

In the brute force solution to our problem, we will run a nested loop. The outer loop will traverse through each element in the array, while the inner loop will compare it with the elements after it to find the next greater and smaller element for every element.

At a glance, the method seems simple to think of and implement, but because of the nested loop, it has a time complexity of O(n^{2}), which isnâ€™t optimal.

Pretty easy yet complex, huh?

Algorithm

Step 1: Start the outer loop from 0 to the arrayâ€™s length and initialise a temporary variable (temp) with -1.

Step 2: Start the inner loop from i+1 to the size of the array.

Step 3: Check if the inner loop element is less than the outer loop element.

Step 4: If yes, print the element, assign 1 to temp and break out of the inner loop.

Step 5: Repeat the same procedure to find the next greater element for each element.

Step 6: Print the arrays â€śsmallerâ€ť and â€śgreaterâ€ť as the answers.

C++ Implementation

#include <iostream>
using namespace std;
void NextGreater(int arr[], int n){
for(int i=0;i<n;i++){
int temp=-1;
for(int j=i+1;j<n;j++){
if(arr[j]>arr[i]){
temp=arr[j];
cout<<temp<<" ";
break;
}
}
if(temp==-1){
cout<<temp<<" ";
}
}
}
void NextSmaller(int arr[], int n){
for(int i=0;i<n;i++){
int temp=-1;
for(int j=i+1;j<n;j++){
if(arr[j]<arr[i]){
temp=arr[j];
cout<<temp<<" ";
break;
}
}
if(temp==-1){
cout<<temp<<" ";
}
}
}
int main(){
int arr[]={2,13,10,6,3,9};
cout<<"Next Greater Element are"<<endl;
NextGreater(arr,6);
cout<<endl;
cout<<"Next Smaller Element are"<<endl;
NextSmaller(arr,6);
}

Output

Next Greater Element are
13 -1 -1 9 9 -1
Next Smaller Element are
-1 10 6 3 -1 -1

Java Implementation

class Main
{
// Find the next greater element for every array element
public static void findNextGreater_And_SmallerElements(int[] input)
{
// base case
if (input == null) {
return;
}
// do for each element
for (int i = 0; i < input.length; i++)
{
// keep track of the next greater element for element `input[i]`
int next = -1;
// process elements on the right of element `input[i]`
for (int j = i + 1; j < input.length; j++)
{
// break the inner loop at the first larger element on the
// right of element `input[i]`
if (input[j] > input[i])
{
next = input[j];
break;
}
}
System.out.print(next + " ");
}
System.out.println();
for (int i = 0; i < input.length; i++)
{
// keep track of the next greater element for element `input[i]`
int next = -1;
// process elements on the right of element `input[i]`
for (int j = i + 1; j < input.length; j++)
{
// break the inner loop at the first larger element on the
// right of element `input[i]`
if (input[j] < input[i])
{
next = input[j];
break;
}
}
System.out.print(next + " ");
}
}
public static void main(String[] args)
{
int[] input = {2,13,10,6,3,9};
findNextGreater_And_SmallerElements(input);
}
}

Output

13 -1 -1 9 9 -1
-1 10 6 3 -1 -1

Python Implementation

def findNextGreaterElements(input):
# base case
if not input:
return
# do for each element
for i in range(len(input)):
# keep track of the next greater element for element `input[i]`
next = -1
# process elements on the right of element `input[i]`
for j in range(i + 1, len(input)):
# break the inner loop at the first larger element on the
# right of element `input[i]`
if input[j] > input[i]:
next = input[j]
break
print(next, end=' ')
if __name__ == '__main__':
input = [2,13,10,6,3,9]
findNextGreaterElements(input)

Output

13 -1 -1 9 9 -1

The Time Complexity- O(n*n)

This method isnâ€™t the best due to its O(n^{2}) time complexity. So now you may be wondering, what is the best approach? Letâ€™s find out!

In this method, we will have to traverse through the array only once because of the stackdata structure. Let us understand how that works by finding the next greater element.

Here, we will have a counter, say i, which will traverse through the array,

an output array to store answers (of the same length as the given array) initialized with -1 and an empty stack.

To begin with, when the stack is empty, the first element of the array will be pushed into it.

Once there is an element in the stack, we will check whether the current element from the array is greater than the top element in the stack.

If yes, pop the element from the stack, and store the current element from the array as the next greater element. Continue checking and popping until the top < current element or the stack is empty.

After that, push the current element from the array into the stack.

For the next element in the array,

Here, 3 isnâ€™t greater than 7, so we will push it.

For the subsequent elements,

As we can see, the final answer matches what we had seen in the problem statement and the brute force solution.

We can also find the next smaller element similarly by just changing the checking condition.

Algorithm

Step 1: Initialise an array, say answer (with the same size as the given array), with -1, and create a stack.

Step 2: In a loop, start traversing through the array.

Step 3: If the stack isnâ€™t empty and the current element in the array is greater than the top element in the stack, pop the elements from the stack. Also, add the current element in the array to the answer array in the corresponding positions.

Step 4: After the condition mentioned above is not fulfilled, push the current element from the array into the stack.

Step 5: Return the answer array, which contains the next greater elements for each element.

Step 6: Repeat all the steps mentioned above to find the next smaller element for each element, replacing the â€śgreater thanâ€ť condition with â€śless thanâ€ť in step 3.

C++ Implementation

#include<bits/stdc++.h>
vector<int> findNextGreaterElements(vector<int>&arr)
{
int n=arr.size();
vector<int>answer(n,-1) //creates the answer array
stack<int> s; //creating an empty stack
for (int i = 0; i < n; i++) //traversing through the elements in the array
{
while (!s.empty() && arr[s.top()] < arr[i]) //finds next greater element
{
answer[s.pop()] = arr[i];
}
s.push(i);
}
return answer;
}
//Method to find the next smaller element for every array element
vector<int> findNextSmallerElements(vector<int>&arr)
{
int n=arr.size();
vector<int>answer(n,-1); //creates the final array
stack<int> s; //creating an empty stack
for (int i = 0; i < n; i++) //traversing through the elements in the array
{
while (!s.empty() && arr[s.top()] > arr[i]) //finds next smaller element
{
answer[s.pop()] = arr[i];
}
s.push(i);
}
return answer;
}
int main()
{
int n,x;
cin>>n;
vector<int>input;
for(int i=0;i<n;i++){
cin>>x;
input.push_back(x);
}
vector<int>result = findNextGreaterElements(input);
cout<<"Next Greater Elements are"<<endl;
for(auto a:result){
cout<<a<<" ";
}
cout<<endl;
result = findNextSmallerElements(input);
cout<<"Next Greater Elements are"<<endl;
for(auto a:result){
cout<<a<<" ";
}
}

Output

Next Greater Elements are
7 8 5 6 6 8 -1
Next Smaller Elements are
-1 3 -1 4 -1 -1 -1

Java Implementation

import java.util.Arrays;
import java.util.Stack;
class Main
{
//Method to find the next greater element for every array element
public static int[] findNextGreaterElements(int[] arr)
{
if (arr == null) //checks if the array is empty
{
return arr;
}
int[] answer = new int[arr.length]; //creates the answer array
Arrays.fill(answer, -1);
Stack<Integer> s = new Stack<>(); //creating an empty stack
for (int i = 0; i < arr.length; i++) //traversing through the elements in the array
{
while (!s.isEmpty() && arr[s.peek()] < arr[i]) //finds next greater element
{
answer[s.pop()] = arr[i];
}
s.push(i);
}
return answer;
}
//Method to find the next smaller element for every array element
public static int[] findNextSmallerElements(int[] arr)
{
if (arr == null) //checks if the array is empty
{
return arr;
}
int[] answer = new int[arr.length]; //creates the final array
Arrays.fill(answer, -1);
Stack<Integer> s = new Stack<>(); //creating an empty stack
for (int i = 0; i < arr.length; i++) //traversing through the elements in the array
{
while (!s.isEmpty() && arr[s.peek()] > arr[i]) //finds next greater element
{
answer[s.pop()] = arr[i];
}
s.push(i);
}
return answer;
}
public static void main(String[] args)
{
int[] input = { 2, 7, 3, 5, 4, 6, 8 };
int[] result = findNextGreaterElements(input);
System.out.println("Next Greater Elements are");
System.out.println(Arrays.toString(result));
result = findNextSmallerElements(input);
System.out.println("Next Smaller Elements are");
System.out.println(Arrays.toString(result));
}
}

Output

Next Greater Elements are
7 8 5 6 6 8 -1
Next Smaller Elements are
-1 3 -1 4 -1 -1 -1

Python Implementation

# Find the next greater element for every array element
def findNextGreaterElements(input):
# base case
if not input:
return
print("Next Greater Elements are")
# do for each element
for i in range(len(input)):
# keep track of the next greater element for element `input[i]`
next = -1
# process elements on the right of element `input[i]`
for j in range(i + 1, len(input)):
# break the inner loop at the first larger element on the
# right of element `input[i]`
if input[j] > input[i]:
next = input[j]
break
print(next, end=' ')
def findNextSmallerElements(input):
# base case
if not input:
return
print("Next Smaller Elements are")
# do for each element
for i in range(len(input)):
# keep track of the next greater element for element `input[i]`
next = -1
# process elements on the right of element `input[i]`
for j in range(i + 1, len(input)):
# break the inner loop at the first larger element on the
# right of element `input[i]`
if input[j] < input[i]:
next = input[j]
break
print(next, end=' ')
if __name__ == '__main__':
input = [2, 7, 3, 5, 4, 6, 8]
findNextGreaterElements(input)
findNextSmallerElements(input)

Output

Next Greater Elements are
7 8 5 6 6 8 -1
Next Smaller Elements are
-1 3 -1 4 -1 -1 -1

Time and space Complexity for all three programs

Time Complexity

O(N) as we are traversing the input array only once.

Space Complexity

O(N), as an extra stack is used to keep track of the elements.

How do we find the next greater and smaller element for every element in an array?

There are two methods to find the next smaller and greater element for every element in an array - The brute force method and Using stack.

What is the time complexity for the two methods to find the next greater and smaller element for every element?

The time complexity for the brute force method is O(n^{2}), and the time complexity for the algorithm using stack is O(n).

Which method is better to find the next greater and smaller element for every element?

The stack method is better to find the next greater and smaller element for every element in arrays.

Why is the method using stack better to find the next greater and smaller element for every element?

The stack method is better since it has a linear time complexity (O(n)).

What is the best complexity to find the next greater and smaller element for every element in an array?

The best complexity is O(n).

Conclusion

This article taught us how to find the next greater and smaller element for every element in an array. As mentioned before, this is a question that is commonly asked in the coding rounds of interviews. So, our aim should be to have a complete understanding of the topic.