Next greater element in an array

Easy, yet sweeet

Hello! 

Today, we’re talking about a problem that’s commonly asked in tech interviews. Tbh, I was asked this very question in my interview for an internship at Amazon, and to be even more honest, I could get it right only too late. 

So, I thought :

So, the problem is, that given an array, you’re supposed to find the next greater element, for every element of that array, and if one doesn’t exist, give -1. 

For instance, for an array A = [1, 3, 4, 2, 0], you’d get

next = [3, 4, -1, -1, -1]. 

The brute force solution should be pretty straightforward. We loop through the array, and check all the elements AFTER the particular element we are at, if it’s bigger. If we reach the end, that means the particular element doesn’t have a next greater element. 

Time complexity?

For the first element, we check elements from the second to the last element, in the worst case. That’s n-1 checks. For the second, n-2, and so on. For the kth(index = k-1) element, we make n-k checks. Thus, 

total checks = n-1 + n-2 + n-3 + …..1 = n*(n-1)/2 

Which is O(N^2). 

Space complexity is O(1). 

Optimized solution

Thought process : 

For every element, only the elements AFTER matter. We are least bothered with the ones BEFORE.

A one side only movement……SPOT ON! STACK! Let’s see how that works

The last element will always give a -1, since there is no next element.

A particular element will be the NGE for all elements before it, until a larger element comes. This larger element will be the NGE for all elements before, until a larger element comes, and so on. This continues until we reach the first element.

Thus, if we go reverse, that is, from last to first in the array, we can employ this logic.

Time complexity : There’s a while loop, inside of a for loop, which can make some people confuse it as O(N^2). However, do note that inside the while loop, there’s only one operation, and that is s.pop(), which takes O(1) time. So, the while loop will be constant time, thus bringing the overall complexity to be O(N), where N is the size of the array. 

Space complexity : We are using a stack, which, in the worst case, can hold all elements of the array, making the complexity as O(N).

As always, the probe is available on my blog here, the code on GitHub. Please do share DKProbesCode with anyone who you think might like it.

Apologies for a lack of memes in this one, I am a little stretched on time here, will get back with better ones in the next probe.

There won’t be a probe this Thursday, so I’ll see you next Tuesday.

Until then

DKP

ITUS(International Talent of Ultimate Student)