Next Greater Element - 2 - AlgoArena Witeso

Intuition:

The only difference between this problem and the earlier problem is that the array is circular in nature in this problem.

Handling circular arrays:

One way is to double the array by pushing all the elements of array at the back in order. But this will cost an extra space for only storing elements, making it an unpreferrable method.

The preferred way to handle circular array is to use the modulus operator that will help in traversing the array in a circular manner. This will double the array hypothetically saving the extra space.
Example: Consider the following image:
(image link)
Hence, it is clear that the array can be traversed in a loop using the modulus operator with the size of array.

Now, the brute force way 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 (that will traverse the array in a circular manner) to check all the elements. In case there is no larger element found, the next greater element will be set to -1.

Approach:

Initialize an answer array 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 next greater element must be found.
Use a nested for loop to traverse the array (in a circular fashion, using modulus operator) to find the next greater element. If found, store the answer in the 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 circular array */
    vector<int> nextGreaterElements(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=1; j < n; j++) {
                
                // Getting the hypothetical index
                int ind = (j+i) % n;
                
                // If the next greater element is found
                if(arr[ind] > currEle) {
                    
                    // Store the next greater element
                    ans[i] = arr[ind];
                    
                    // Break from the loop
                    break;
                }    
            }
        }
       
        // Return the answer
        return ans;
    }
};

int main() {
    int n = 6;
    vector<int> arr = {5, 7, 1, 7, 6, 0};
   
    /* 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.nextGreaterElements(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 circular array */
    public int[] nextGreaterElements(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 = 1; j < n; j++) {
               
                // Getting the hypothetical index
                int ind = (j + i) % n;
               
                // If the next greater element is found
                if(arr[ind] > currEle) {
                   
                    // Store the next greater element
                    ans[i] = arr[ind];
                   
                    // Break from the loop
                    break;
                }    
            }
        }
       
        // Return the answer
        return ans;
    }

    public static void main(String[] args) {
        int n = 6;
        int[] arr = {5, 7, 1, 7, 6, 0};
       
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
       
        /* Function call to find the next greater element
        for each element in the circular array */
        int[] ans = sol.nextGreaterElements(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 circular array
    def nextGreaterElements(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(1, n):
               
                # Getting the hypothetical index
                ind = (j + i) % n
               
                # If the next greater element is found
                if arr[ind] > currEle:
                   
                    # Store the next greater element
                    ans[i] = arr[ind]
                   
                    # Break from the loop
                    break
       
        # Return the answer
        return ans

if __name__ == "__main__":
    n = 6
    arr = [5, 7, 1, 7, 6, 0]
   
    # Creating an instance of 
    # Solution class
    sol = Solution()
   
    # Function call to find the next greater element
    # for each element in the circular array
    ans = sol.nextGreaterElements(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 circular array */
    nextGreaterElements(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 = 1; j < n; j++) {
               
                // Getting the hypothetical index
                let ind = (j + i) % n;
               
                // If the next greater element is found
                if(arr[ind] > currEle) {
                   
                    // Store the next greater element
                    ans[i] = arr[ind];
                   
                    // Break from the loop
                    break;
                }    
            }
        }
       
        // Return the answer
        return ans;
    }
}

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

let n = 6;
let arr = [5, 7, 1, 7, 6, 0];

/* Function call to find the next greater element
for each element in the circular array */
let ans = sol.nextGreaterElements(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:

Since the better way to solve this problem is already discussed in the Next greater element problem which is by using a stack. The only thing left to handle in this problem is circular nature of array.

Handling circular arrays:

Since, we have to start the traversal from the back of the hypothetically doubled array, we must perform the stack operations for all elements. But the next greater element must be stored only for the second half of elements skipping the first half (as they are hypothetical elements).

Approach:

Initialize an answer array to store the next greater elements for the given array. Declare a stack data structure.
Start traversing the hypothetically doubled array from back using the modulus operator. For the current element, pop the elements from stack till the top is less than or equal to the current element.
For the first half of the elements, discard the greatest element if found. For the second half of the elements, if a greater element is found, store it in the answer array, otherwise store -1. Push the current element on top of stack (for both halves).
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> nextGreaterElements(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 LIF fashion
        stack<int> st;
        
        // Start traversing from the back
        for(int i = 2*n-1; i >= 0; i--) {
            
            // Get the actual index
            int ind = i % n;
            
            // Get the current element
            int currEle = arr[ind];
            
            /* 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();
            }
            
            // Store the answer for the second half
            if(i < n) {
                
                /* 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 = 6;
    vector<int> arr = {5, 7, 1, 7, 6, 0};
    
    /* 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.nextGreaterElements(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[] nextGreaterElements(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 = 2 * n - 1; i >= 0; i--) {
            
            // Get the actual index
            int ind = i % n;
            
            // Get the current element
            int currEle = arr[ind];
            
            /* 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();
            }
            
            // Store the answer for the second half
            if (i < n) {
                
                /* 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 = 6;
        int[] arr = {5, 7, 1, 7, 6, 0};
        
        /* 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.nextGreaterElements(arr);
        
        System.out.print("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 nextGreaterElements(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(2 * n - 1, -1, -1):
            
            # Get the actual index
            ind = i % n
            
            # Get the current element
            currEle = arr[ind]
            
            # 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()
            
            # Store the answer for the second half
            if i < n:
                
                # If the greater element is not 
                # found, stack will be empty
                if st:
                    ans[i] = st[-1]
            
            # Push the current element in the stack 
            # maintaining the decreasing order
            st.append(currEle)
        
        # Return the result
        return ans

# Driver Code
if __name__ == "__main__":
    arr = [5, 7, 1, 7, 6, 0]
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to find the next greater 
    # element for each element in the array
    ans = sol.nextGreaterElements(arr)
    
    print("The next greater elements are:", ans)
class Solution {
    
    /* Function to find the next greater 
    element for each element in the array */
    nextGreaterElements(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 = 2 * n - 1; i >= 0; i--) {
            
            // Get the actual index
            let ind = i % n;
            
            // Get the current element
            let currEle = arr[ind];
            
            /* 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();
            }
            
            // Store the answer for the second half
            if (i < n) {
                
                /* If the greater element is not 
                found, stack will be empty */
                if (st.length > 0) 
                    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;
    }
}

// Driver Code
let arr = [5, 7, 1, 7, 6, 0];

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

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

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

Complexity Analysis:

Time Complexity: O(N) (where N is the size of the array)
Traversing on the array takes O(N) time and traversing the stack will take overall O(N) 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

Next Greater Element - 2

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Handling circular arrays:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Handling circular arrays:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts