## Introduction

Stack is one of the most elementary data structures and has a wide range of applications. There are numerous problems that can be solved using stacks. These problems are also asked in interviews with top tech companies. This blog will discuss the various approaches to solve the problem distance from the next greater element.

There are many approaches to solving this problem, but we should look at some examples to understand the problem better before discussing them.

**Some Examples**

**Input:**

arr[] = {1,2,3,2,5}

**Output:**

{1,1,2,1,0}

Explanation:

- The next greater element for 1 is 2 which is at position 2 therefore the distance =
*2 - 1 = 1.* - The next greater element for 2 is 3 which is at position 3 therefore the distance =
*3 - 2 = 1.* - The next greater element for 3 is 5 which is at position 5 therefore the distance =
*5 - 3 = 2.* - The next greater element for 2 is 5 which is at position 5 therefore the distance =
*5 - 4 = 1.* - There is no next greater element for five before discussing them. Therefore, the distance is 0.

**Input:**

arr[] = {4,3,2,9}

**Output:**

{3,2,1,0}

Explanation:

- The next greater element for 4 is nine at position 4; therefore, the distance = 4 - 1 = 3.
- The next greater element for 3 is 9 which is at position 4 therefore the distance = 4 - 2 = 2.
- The next greater element for 2 is 9 which is at position 4 therefore the distance = 4 - 3 = 1.
- There is no next greater element for 9; therefore, distance is 0.

## Brute Force Approach

The brute force approach for this problem of finding the distance from next greater element is to traverse in the right direction for every element, find the primary or next greater element, and then calculate the distance from this greater element and the current element.

### Algorithm

- Create a function distance_from_next_greater() that takes one parameter, which is the array given to us.
- In the function, we will traverse two nested for loops, and every element, we will find its next greater element by traveling in the inner for loop, and when we find it, we break from the loop and calculate the distance stored.
- After that, we will return the array in which we have stored the answer.

### Code in C++

```
// C++ code for Distance from Next Greater element
#include <bits/stdc++.h>
using namespace std;
vector<int> distance_from_next_greater(vector<int> a)
{
int N = a.size();
// Using two for loops to get the distance of next
// greater element for every element
for (int i = 0; i < N; i++)
{
int distance = 0;
for (int j = i + 1; j < N; j++)
{
if (a[j] > a[i])
{
// finding next greater element
// storing distance and breaking from the loop
distance = j - i;
break;
}
}
// storing the answer in the array
a[i] = distance;
}
return a;
}
// Driver code
int main()
{
vector<int> arr = {7, 2, 1, 4, 6};
vector<int> ans = distance_from_next_greater(arr);
for (int i = 0; i < ans.size(); i++)
{
cout << ans[i] << " ";
}
}
```

```
Input: 7 2 1 4 6
Output: 0 2 1 1 0
```

### Complexity Analysis

**Time Complexity: **O(N*N)

Since we are using two nested loops and for every element, we are traversing from the index of that element to N, and we are finding a greater element than the current element, so in the worst case, if we don’t find any element we will traverse till N. Therefore the time complexity will be the sum of N+N-1+N-2+N-3+ …1, and the sum of this series will be (N*(N+1))/2. If the values of N are large, then this sum would be approximately equal to N*N.

**Space Complexity: **O(1)

Since we are not using any extra array to store the answer, the space complexity of the above solution is O(1).