Distance from Next Greater element

Vibhor Bhatnagar
Last Updated: May 13, 2022

Introduction  

This blog will discuss the various approaches to solve the problem distance from 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

  1. Create a function distance_from_next_greater() that takes one parameter, which is the array given to us. 
  2. 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.
  3.  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).

Optimized Approach

In the above-discussed approach, the complexity is very high, and therefore, we need to develop a more efficient approach.

So in this approach, we will find the next greater element by application of stack, and whenever we find any greater element, we will store the answer in the array.

Algorithm

  1. We will maintain a stack of pairs that will contain all the elements in a non-increasing fashion.
  2. We will check if the current element of the array is greater than the element at the top of the stack.
  3. After that, we will keep popping the elements from the stack till we find any element smaller than the current element of the array. If we find any element smaller, we will calculate the answer and pop the top element of the stack.
  4. The current element will be pushed into the stack, and the process will be repeated until the loop is over.

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();
    // for storing the answer
    vector<int> ans(n);
  
  // stack pair to store the value of element and index of the element
    stack<pair<int, int>> st;
  
    // for last element the answer is always zero
    ans[n - 1] = 0;

    // pushing the last element in the stack
    st.push({a[n - 1], n - 1});

    for (int i = n - 2; i >= 0; i--)
    {
        if (a[i] < st.top().first)
        {
            // storing answer for a[i]
            ans[i] = st.top().second - i;
            // pushing the value a[i] and
            // the index i in the stack
            st.push({a[i], i});
        }
        else
        {
            while (st.empty() ==false && a[i] >= st.top().first)
            {
                // popping elements till a[i] is
                // greater than the top element of
                // the stack
                st.pop();
            }
            if (!st.empty())
            {
                // if the stack is not empty repeating
                // the above process
                ans[i] = st.top().second - i;
                st.push({a[i], i});
            }
            else
            {
                // else the answer for a[i] is zero
                st.push({a[i], i});
                ans[i] = 0;
            }
        }
    }

    return ans;
}

// Driver code
int main()
{
    vector<int> arr = {9, 1, 9, 10, 2, 3};

    vector<int> ans = distance_from_next_greater(arr);

    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << " ";
    }
}

 

Input: 9 1 9 10 2 3
Output: 3 1 1 0 1 0 

Complexity Analysis

Time Complexity: O(N)

Since we are doing single traversal, therefore, the time complexity is O(N).

Space Complexity: O(N)

Since we store our answer in another array, the space complexity will be O(N).

Frequently asked questions

Q1. What is a stack?

Ans. Stack is a linear data structure, and it is based on the principle of LIFO (Last In First Out).

 

Q2. What is space complexity?

Ans. The space complexity of an algorithm is the overall space taken by algorithm w.r.t input size.

 

Q3. What is time complexity?

Ans. The time complexity of an algorithm can be defined as the time taken by the computer to run an algorithm.

Key takeaways

In this article, we discussed the problem distance from next greater element. We have also discussed two approaches to this problem. The first one is the brute force solution. The second is the optimal solution implemented using a stack.

We hope you gained some insight into this problem, and now it is your turn to practice this problem and code it out in your way. 

Don’t Stop here; try more problems and gain some more expertise in DSA!

  1. Next Greater Element
  2. Least Greater Element
  3. Next Smaller Element
  4. Kth Smallest Element

 

Until then, Keep Learning and Keep Coding.


Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think