Distance from Next Greater Element

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] << " ";
    }
}

You can also try this code with Online C++ Compiler

Run Code

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

What is a stack?

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

What is space complexity?

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

What is time complexity?

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

Conclusion

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

Recommended Reading:

• Add Two Elements Represented by Stack
• Next Greater Element using a Monotonic Stack
• Maximum range length such that A[i] is maximum in the given range for all i from [1, N]
• Create Maximum Number
• Daily Temperatures
• Aptitude Preparation

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, Keep Learning and Keep Coding.