Next Greater Element

Intuition:

A naive approach to solve this question will be to use a loop to pick up an element of the array, and then find its next greater element using a nested loop. In case there is no larger element found on the right of the current element, the next greater element will be set to -1.

Approach:

Initialize an array answer to store the next greater elements for the given array with all elements initially set to -1.
Traverse the array using a for loop to select the current element for which the next greater element must be found.
Use a nested for loop to traverse the right side of the array (from the current element) to find the next greater element. If found, store the answer in the answer array and break from the inner loop.
Once the outer for loop ends, the answer array storing the result can be returned.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    /* Function to find the next greater 
    element for each element in the array */
    vector<int> nextLargerElement(vector<int> arr) {
        
        int n = arr.size(); // size of array
        
        // To store the next greater elements
        vector<int> ans(n, -1);
        
        for(int i=0; i < n; i++) {
            
            // Get the current element+
            int currEle = arr[i];
            
            /* Nested loop to get the 
            next greater element */
            for(int j=i+1; j < n; j++) {
                
                // If the next greater element is found
                if(arr[j] > currEle) {
                    
                    // Store the next greater element
                    ans[i] = arr[j];
                    
                    // Break from the loop
                    break;
                }    
            }
        }
        
        // Return the answer
        return ans;
    }
};

int main() {
    int n = 4;
    vector<int> arr = {1, 3, 2, 4};

    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the next greater element
    for each element in the circular array */
    vector<int> ans = sol.nextLargerElement(arr);
    
    cout << "The next greater elements are: ";
    for(int i=0; i < n; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {

    /* Function to find the next greater 
    element for each element in the array */
    public int[] nextLargerElement(int[] arr) {
        
        int n = arr.length; // size of array
        
        // To store the next greater elements
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        
        for(int i = 0; i < n; i++) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Nested loop to get the 
            next greater element */
            for(int j = i + 1; j < n; j++) {
                
                // If the next greater element is found
                if(arr[j] > currEle) {
                    
                    // Store the next greater element
                    ans[i] = arr[j];
                    
                    // Break from the loop
                    break;
                }    
            }
        }
        
        // Return the answer
        return ans;
    }

    public static void main(String[] args) {
        int n = 4;
        int[] arr = {1, 3, 2, 4};
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to find the next greater element
        for each element in the array */
        int[] ans = sol.nextLargerElement(arr);
        
        System.out.println("The next greater elements are: ");
        for(int i = 0; i < n; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
class Solution:

    # Function to find the next greater 
    # element for each element in the array
    def nextLargerElement(self, arr):
        
        n = len(arr) # size of array
        
        # To store the next greater elements
        ans = [-1] * n
        
        for i in range(n):
            
            # Get the current element
            currEle = arr[i]
            
            # Nested loop to get the 
            # next greater element
            for j in range(i + 1, n):
                
                # If the next greater element is found
                if arr[j] > currEle:
                    
                    # Store the next greater element
                    ans[i] = arr[j]
                    
                    # Break from the loop
                    break
        
        # Return the answer
        return ans

if __name__ == "__main__":
    n = 4
    arr = [1, 3, 2, 4]
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to find the next greater element
    # for each element in the array
    ans = sol.nextLargerElement(arr)
    
    print("The next greater elements are: ")
    for i in range(n):
        print(ans[i], end=" ")
class Solution {

    /* Function to find the next greater 
    element for each element in the array */
    nextLargerElement(arr) {
        
        let n = arr.length; // size of array
        
        // To store the next greater elements
        let ans = new Array(n).fill(-1);
        
        for(let i = 0; i < n; i++) {
            
            // Get the current element
            let currEle = arr[i];
            
            /* Nested loop to get the 
            next greater element */
            for(let j = i + 1; j < n; j++) {
                
                // If the next greater element is found
                if(arr[j] > currEle) {
                    
                    // Store the next greater element
                    ans[i] = arr[j];
                    
                    // Break from the loop
                    break;
                }    
            }
        }
        
        // Return the answer
        return ans;
    }
}

// Creating an instance of Solution class
let sol = new Solution();

let n = 4;
let arr = [1, 3, 2, 4];

/* Function call to find the next greater element
for each element in the array */
let ans = sol.nextLargerElement(arr);

console.log("The next greater elements are: " + ans.join(" "));

Complexity Analysis:

Time Complexity: O(N²) (where N is the size of given array)
Using two nested for loops to find the next greater elements.

Space Complexity: O(N) The space required to store the answer is O(N).

Intuition:

In order to obtain the next greater element (which will always be on the right side) for a particular element, if we traverse the array from the beginning to the end, it is impossible to know the right elements beforehand as they will be unvisited. But if the traversal is done from the end to the beginning of array, it will be easier to find the next greater element cause all the right elements will be already visited(known) to us. Thus, we will start the traversal from back and the whole discussion will be based on the same.

Now since, we are traversing from the back, the question is now to find the last greatest element. Hence, no matter how many greater elements we encounter, the only greater element we must consider first is the last greater element that was seen. This gives an idea of using stack data structure because it stores elements in the Last In First Out fashion. Now, comes the question of how to store the elements in the stack?

Understanding:

Since, we are considered about the greater elements only, it makes sense to store(push) the elements in the stack in a decreasing order (smaller elements are on the top and larger elements on the bottom). So that for every element that we found, the stack already contains greater elements (potentially).

But it is not always guaranteed that the top of the stack will be greater than the current element (for which the next greater element is to be found). In such scenarios, we can pop elements from the stack till we get a greater element. If a greater element is found, it can be stored as the answer otherwise -1 can be stored as answer. Once the answer is stored, the current element can be stored in the stack maintaining the decreasing order of elements.

Approach:

Initialize an answer array to store the next greater elements for the given array. Declare a stack data structure.
Start traversing the array from back. For current element, pop the elements from stack till the top is less than or equal to the current element.
If a greater element is found, store it in the answer array, otherwise store -1. Push the current element in the stack maintaining decreasing order.
Once the traversal on array is complete, the answer array stores the result.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    /* Function to find the next greater 
    element for each element in the array */
    vector<int> nextLargerElement(vector<int> arr) {
        
        int n = arr.size(); //size of array
        
        // To store the next greater elements
        vector<int> ans(n);
        
        // Stack to get elements in LIFO fashion
        stack<int> st;
        
        // Start traversing from the back
        for(int i=n-1; i >= 0; i--) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the greater element */
            while(!st.empty() && st.top() <= currEle) {
                st.pop();
            }
            
            /* If the greater element is not 
            found, stack will be empty */
            if(st.empty()) 
                ans[i] = -1;
                
            // Else store the answer
            else 
                ans[i] = st.top();
            
            /* Push the current element in the stack 
            maintaining the decreasing order */
            st.push(currEle);
        }
        
        // Return the result
        return ans;
    }
};

int main() {
    int n = 4;
    vector<int> arr = {1, 3, 2, 4};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the next greater 
    element for each element in the array */
    vector<int> ans = sol.nextLargerElement(arr);
    
    cout << "The next greater elements are: ";
    for(int i=0; i < n; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {

    /* Function to find the next greater 
    element for each element in the array */
    public int[] nextLargerElement(int[] arr) {
        
        int n = arr.length; // size of array
        
        // To store the next greater elements
        int[] ans = new int[n];
        
        // Stack to get elements in LIFO fashion
        Stack<Integer> st = new Stack<>();
        
        // Start traversing from the back
        for(int i = n - 1; i >= 0; i--) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the greater element */
            while(!st.isEmpty() && 
                  st.peek() <= currEle) {
                st.pop();
            }
            
            /* If the greater element is not 
            found, stack will be empty */
            if(st.isEmpty()) 
                ans[i] = -1;
                
            // Else store the answer
            else 
                ans[i] = st.peek();
            
            /* Push the current element in the stack 
            maintaining the decreasing order */
            st.push(currEle);
        }
        
        // Return the result
        return ans;
    }

    public static void main(String[] args) {
        int n = 4;
        int[] arr = {1, 3, 2, 4};
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to find the next greater 
        element for each element in the array */
        int[] ans = sol.nextLargerElement(arr);
        
        System.out.println("The next greater elements are: ");
        for(int i = 0; i < n; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
class Solution:

    # Function to find the next greater 
    # element for each element in the array
    def nextLargerElement(self, arr):
        
        n = len(arr) # size of array
        
        # To store the next greater elements
        ans = [-1] * n
        
        # Stack to get elements in LIFO fashion
        st = []
        
        # Start traversing from the back
        for i in range(n - 1, -1, -1):
            
            # Get the current element
            currEle = arr[i]
            
            # Pop the elements in the stack until 
            # the stack is not empty and the top 
            # element is not the greater element
            while st and st[-1] <= currEle:
                st.pop()
            
            # If the greater element is not 
            # found, stack will be empty
            if not st:
                ans[i] = -1
            else:
                # Else store the answer
                ans[i] = st[-1]
            
            # Push the current element in the stack 
            # maintaining the decreasing order
            st.append(currEle)
        
        # Return the result
        return ans

if __name__ == "__main__":
    n = 4
    arr = [1, 3, 2, 4]
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to find the next greater 
    # element for each element in the array
    ans = sol.nextLargerElement(arr)
    
    print("The next greater elements are: ", end="")
    for i in range(n):
        print(ans[i], end=" ")
class Solution {

    /* Function to find the next greater 
    element for each element in the array */
    nextLargerElement(arr) {
        
        let n = arr.length; // size of array
        
        // To store the next greater elements
        let ans = new Array(n).fill(-1);
        
        // Stack to get elements in LIFO fashion
        let st = [];
        
        // Start traversing from the back
        for(let i = n - 1; i >= 0; i--) {
            
            // Get the current element
            let currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the greater element */
            while(st.length > 0 && 
                  st[st.length - 1] <= currEle) {
                st.pop();
            }
            
            /* If the greater element is not 
            found, stack will be empty */
            if(st.length === 0) 
                ans[i] = -1;
            else 
                // Else store the answer
                ans[i] = st[st.length - 1];
            
            /* Push the current element in the stack 
            maintaining the decreasing order */
            st.push(currEle);
        }
        
        // Return the result
        return ans;
    }
}

// Creating an instance of Solution class
let sol = new Solution();

let n = 4;
let arr = [1, 3, 2, 4];

/* Function call to find the next greater 
element for each element in the array */
let ans = sol.nextLargerElement(arr);

console.log("The next greater elements are: " + ans.join(" "));

Complexity Analysis:

Time Complexity: O(N) (where N is the size of the array)
Traversing on the hypothetical array takes O(2N) time and traversing the stack will take overall O(2N) time as all the elements are pushed in the stack once.

Space Complexity: O(N)
The answer array takes O(N) space and the space used by stack will be O(N) in the worst case.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Understanding:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code