Posted on by Kalkicode
Code Stack

# Find the next greater element on right side

The problem "Find the next greater element on the right side" involves taking an array of integers as input and, for each element in the array, finding the next greater element that appears to its right side. If no such element is found, the output for that element will be -1. The goal is to find and print this next greater element for each element in the array.

## Problem Statement

Given an array of integers, we need to find the next greater element on the right side for each element in the array.

## Example

Let's consider the following input array:

``[6, 5, 6, 10, 5, 9, 7, 11, 9, 10]``

The output will be as follows:

``````6 → 10
5 → 9
6 → 10
10 → 11
5 → 9
9 → 11
7 → 11
11 → -1
9 → 10
10 → -1
``````

## Idea to Solve the Problem

To solve this problem, we can use a stack data structure to keep track of the elements that we have encountered so far. We traverse the input array from left to right, and for each element, we compare it with the top element of the stack.

1. If the stack is empty or the current element is less than or equal to the top element of the stack, we push the current element into the stack.

2. If the current element is greater than the top element of the stack, we keep popping elements from the stack until we find an element that is greater than the current element. For each element popped from the stack, the next greater element on the right side is the current element. We print the pair (popped element → current element).

3. After traversing the whole array, we pop the remaining elements from the stack and print their next greater element as -1.

## Algorithm

1. Create a stack data structure to hold elements.
2. Traverse the input array from left to right.
3. For each element in the array: a. If the stack is empty or the current element is less than or equal to the top element of the stack, push the current element into the stack. b. If the current element is greater than the top element of the stack, keep popping elements from the stack until the top element is greater than the current element. For each element popped, print the pair (popped element → current element).
4. After the loop, pop the remaining elements from the stack and print their next greater element as -1.

## Pseudocode

``````Function nextGreater(arr, size):
Create a stack 's'
For i = 0 to size - 1:
while s is not empty and s.top >= arr[i]:
print s.pop() + " → " + arr[i]
s.push(arr[i])
while s is not empty:
print s.pop() + " → -1"
``````

## Time Complexity

The time complexity of the algorithm is O(n), where n is the number of elements in the input array. This is because we traverse the array once, and for each element, we perform a constant amount of work (push and pop operations on the stack). Therefore, the overall time complexity is linear in the size of the input array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post