Next Greater Element using Stack

Table of contents:

1. Problem statement
2. Brute Force approach
3. Approach using Stack
4. Real World examples.

PROBLEM STATEMENT

Given an array of integers, arr, of length N. The task is to find the Next Greater Element (NGE) for each element in the array. We will solve this problem completely in this OpenGenus article.

For a given element arr[i], the Next Greater Element is the first element to the right of arr[i] that is greater than arr[i]. If there is no such element, the Next Greater Element for that element should be -1.

Example:

arr = [4, 6, 3, 2, 8, 1, 9]
Explanation:
For the element 4, the next greater element to its right is 6.
For the element 6, the next greater element to its right is 8.
For the element 3, the next greater element to its right is 8.
For the element 2, the next greater element to its right is 8.
For the element 8, there is no greater element to its right, so the output is 9.
For the element 1, there is no greater element to its right, so the output is 9.
For the element 9, there is no greater element to its right, so the output is -1.

BRUTEFORCE APPROACH

The brute force approach to solving the Next Greater Element problem involves directly iterating through each element in the input array and comparing it with the elements to its right to find the next greater element.

Intuitive steps:

1. Create an array called result of the same length as the input array. Initialize all elements of this array to -1. This array will store the Next Greater Element for each element in the input array.
2. Start iterating through the elements of the input array one by one.
3. For the current element, start a nested loop to iterate through the remaining elements to its right (indices greater than the current index).
4. Compare each element in the inner loop with the current element. Check if the element in the inner loop is greater than the current element.
5. If you find an element in the inner loop that is greater than the current element:
   Update the value in the result array at the index of the current element with the value of the element you found in the inner loop.
   Break out of the inner loop since you've found the Next Greater Element for the current element.
6. If no greater element is found in the inner loop for the current element:Leave the value in the result array at the index of the current element as -1, indicating that no greater element was found to the right.
7. Continue this process for each element in the input array, updating the result array as needed.
8. Once you have processed all elements in the input array, the result array will contain the Next Greater Elements for each element.
9. The result array is your final output, showing the Next Greater Element for each element in the input array.

Following is the complete C++ implementation of this approach:

#include<bits/stdc++.h>

find_next_greater_elements_bruteforce(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] > arr[i]) {
                result[i] = arr[j];
                break;
            }
        }
    }

    return result;
}

int main() {
  vector<int> arr = {4, 6, 3, 2, 8, 1, 9};
  vector<int> result = find_next_greater_elements_bruteforce(arr);

    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

Explanation:

Example:Input Array: [4, 6, 3, 2, 8, 1, 9]
1.Initialize the result array with -1 values: [-1, -1, -1, -1, -1, -1, -1].

2.Start iterating through the input array:
For the element 4, the inner loop finds the next greater element 6. Update result[0] to 6.
For the element 6, the inner loop finds the next greater element 8. Update result[1] to 8.
For the element 3, the inner loop finds the next greater element 8. Update result[2] to 8.
For the element 2, the inner loop finds the next greater element 8. Update result[3] to 8.
For the element 8, the inner loop doesn't find any greater element. No change to result[4].
For the element 1, the inner loop doesn't find any greater element. No change to result[5].
For the element 9, the inner loop doesn't find any greater element. No change to result[6].

3.The result array after processing all elements: [6, 8, 8, 8, -1, -1, -1].
4.The final output is the result array: [6, 8, 8, 8, -1, -1, -1].
5.So, the Next Greater Elements for the given input array [4, 6, 3, 2, 8, 1, 9] are [6, 8, 8, 8, -1, -1, -1] using the brute force approach.

Time and Space Complexities:

1. This approach has a time complexity of O(n^2), where n is the length of the input array. For each element, you potentially compare it with all the elements to its right, leading to a quadratic number of comparisons.
2. The space complexity is O(n) because you need additional space to store the input array and the result array.

Finding next greater element using Stack

In this Approach, we use a stack to keep track of indices of elements whose next greater element is yet to be determined. We iterate through the array and compare each element with the top of the stack (the element at the top of the stack is the most recent element for which we haven't found the next greater element yet).

If the current element is greater than the element at the top of the stack, we update the result for the element at the index popped from the stack. We repeat this process until we have processed all the elements in the array.

At the end of the iteration, if there are any elements left in the stack, it means there is no greater element to their right, so we set their corresponding result values to -1.

Implementation in C++:

#include<bits/stdc++.h>

vector<int> find_next_greater_elements(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> stack;

    for (int i = 0; i < n; ++i) {
        // While the current element is greater than the top of the stack,
        // update the result for the elements at the indices in the stack.
        while (!stack.empty() && arr[i] > arr[stack.top()]) {
            int idx = stack.top();
            stack.pop();
            result[idx] = arr[i];
        }

        // Push the current index onto the stack.
        stack.push(i);
    }

    return result;
}

int main() {
    vector<int> arr = {4, 6, 3, 2, 8, 1, 9};
    vector<int> result = find_next_greater_elements(arr);

    for (int num : result) {
      cout << num << " ";
    }
    return 0;
}

OUTPUT:
6 8 8 8 9 9 -1

Explanation:

1. We start with an empty stack and an input array arr = {4, 6, 3, 2, 8, 1, 9}. We also create a result vector initialized with -1 for each element.
2. Iterating through the array from left to right, we encounter the first element 4. We push its index 0 onto the stack. (stack: [0])
3. Next, we encounter the element 6. Since 6 is greater than 4, we update the result at index 0 to 6 (result: [6]). We pop the index 0 from the stack as we have found its next greater element. Then, we push the index 1 of the element 6 onto the stack. (stack: [1])
4. Continuing, we encounter the element 3. We compare it with the element at the top of the stack, which is 6. Since 3 is not greater than 6, we do not update the result for the element 6. We push the index 2 of the element 3 onto the stack. (stack: [1, 2])
5. Next, we encounter the element 2. We compare it with the element at the top of the stack, which is 3. Since 2 is less than 3, we do not update the result for the element 3. We push the index 3 of the element 2 onto the stack. (stack: [1, 2, 3])
6. Moving on, we encounter the element 8. Since 8 is greater than the elements in the stack (2, 3, 6, and 4), we update the result for all these elements to 8. We pop each index from the stack as we have found their next greater elements. Then, we push the index 4 of the element 8 onto the stack. (result: [6, 8, 8, 8, 9]). (stack: [1, 4])
7. Next, we encounter the element 1. We compare it with the element at the top of the stack, which is 8. Since 1 is not greater than 8, we do not update the result for the element 8. We push the index 5 of the element 1 onto the stack. (stack: [1, 4, 5])
8. Finally, we encounter the element 9. Since 9 is greater than the element in the stack (1), we update the result for the element 1 to 9. We pop the index 5 from the stack as we have found its next greater element. We do not update the result for the element 9 since it has no greater element to its right. (result: [6, 8, 8, 8, 9, 9]). (stack: [1])
9. At this point, we have processed all elements in the array. The stack is empty, and all the remaining elements in the result vector are already set to their correct values.
10. The resulting vector result contains the Next Greater Elements for each element in the input array arr. The output is 6 8 8 8 9 9 -1, which is the correct answer for the aboveexample.

Time complexities and space complexities:

1. the time complexity of the stack-based approach is O(n), where n is the length of the input array. This is because each element is processed exactly once, and the stack operations are performed in constant time.
2. Combining both the stack space and the result array space, the overall space complexity of the stack-based approach is O(n).

Realworld Examples:

Next Greater Element is a fundamental problem in computer science and finds applications in various real-world scenarios

Here are few of them:

1. Stock Trading Strategy:Traders in the stock market can utilize the stack-based approach to determine optimal entry or exit points for trades. By tracking the Next Greater Element among stock prices, traders can identify potential points to buy or sell shares based on price trends.
2. Task Scheduling:In task scheduling systems, tasks with varying priorities need to be executed efficiently. By applying the stack-based approach, tasks can be prioritized based on their urgency (Next Greater Element) and executed in an organized manner.
3. Network Routing:Routers in computer networks can use the stack-based approach to make routing decisions. Each router can determine the Next Greater Element (higher-capacity route) to forward data packets, ensuring efficient data transmission through the network.
4. Task Priority Management: In operating systems or task management applications, the stack-based approach can assist in managing task priorities. Tasks with higher priority (Next Greater Element) can be executed first, enhancing system responsiveness.