Find next greater element in array or find next greater element to right.
Given an input array, find the next greater element for every element of an array. The next greater element x is the first greater element on the right side of x in an array.
For example:
Example 1:
Input: {4, 2, 6, 8, 1, 0}
Output: {6, 6, 8, -1, -1, -1}
4 => 6 (The first next greater element of 4 is 6)
2 => 6 (Next greater element of 2 is 6)
6 => 8 (Next greater element of 6 is 8)
8 => -1 (No next greater element found)
1 => -1 (No next greater element found)
0 => -1
Example 2:
Input: {7, 8, 1, 4}
Output: {8, -1, 4, -1}
In this tutorial, I am going to discuss multiple approaches to find next greater element to right of an array.
We start with the brute force approach to find the next greater number in an array using two for loops. Then, we improve our solution to solve this problem in O(n) time complexity.
Next Greater Element
Find Greater Element to Right – Brute Force
i) Method 1: Using two for loops
The simplest approach is to use two for loops to find the next greater number in an array.
For every element iterate on the right side of an array to find the first greater element. Break the loop when the first greater element is found.
The time complexity of this approach is O(n2) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Code example public static int[] nextGreaterElement(int[] arr) { int[] output = new int[arr.length]; Arrays.fill(output, -1); for(int i = 0; i < arr.length; i++) { for(int j = i+1; j < arr.length; j++) { if(arr[i] < arr[j]) { output[i] = arr[j]; break; } } } return output; } |
ii) Method 2: Using stack
Find Next Greater Element in Array using Stack – Java Code
In our previous approach, we have solved this problem using two for loops. In this example, we are going to solve this problem in O(n) time complexity using stack data structure.
Here are the following steps to find next greater element to right of an array.
1) Declare a stack which holds value of integer type.
2) If the stack is empty or the element present in a current index is smaller than the top element of the stack, then push the current index on the stack.
3) If element present at current index is greater than the top element of the stack, Pop the index and store the first greater element in an output array.
4) Then, Push index i in a stack.
5) Repeat step 2, 3 and 4 until the array is traversed completely.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
We have discussed two approaches to find the next greater element in an array. Let’s write it’s java code to find the next larger element using stack.
Next greater element video tutorial
Sorting algorithms and their time complexities
Programming questions on the stack – video tutorial
|
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 |
import java.util.Stack; public class NextGreaterElement { public static int[] nextGreaterElement(int[] arr) { int[] output = new int[arr.length]; Arrays.fill(output, -1); //Stack declaration Stack<Integer> st = new Stack<>(); //Traverse an array for (int i = 0; i < arr.length; i++) { while (!st.isEmpty() && arr[st.peek()] < arr[i]) { output[st.pop()] = arr[i]; } st.push(i); } return output; } public static void main(String[] args) { int arr[] = { 4, 2, 6, 8, 1 }; int[] output = nextGreaterElement(arr); System.out.println(Arrays.toString(output)); } } |
Next Greater Element InterviewBit – Java Code
|
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 |
//Next greater element interviewbit public class Solution { public ArrayList nextGreater(ArrayList A) { int[] res = new int[A.size()]; Arrays.fill(res, -1); Stack stack = new Stack<>(); for (int i = 0; i < A.size(); i++) { int num = A.get(i); while (!stack.isEmpty() && num > A.get(stack.peek())) { res[stack.pop()] = num; } stack.push(i); } ArrayList result = new ArrayList<>(); for (int num : res) { result.add(num); } return result; } } |
Next greater element video tutorial
Java program to find first Non-repeated character in a string
