Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction  
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Code in C++
2.3.
Complexity Analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Code in C++
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a stack?
4.2.
What is space complexity?
4.3.
What is time complexity?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Distance from Next Greater Element

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Stacks

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

  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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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:

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.

 

Previous article
Check if stack elements are pairwise consecutive
Next article
Convert Given Binary String S to all 1s by Changing all 0s to 1s in Range [i+1, i+K] if S[i] is ‘1’
Live masterclass