Next greater element

 I came across an interesting problem today, give a list of numbers n1 to n10, we need to return an array which will have the next greater element for each number

for example, for input N =  [...some numbers..] with length L

we need to return

 A = [a1....some numbers..] with length same as N

where A[i] can be zero if there are no greater elements after  N[i], if there is a greater element we need to get the first instance of greater element and put it in answer array A

The simple solution requires bruteforcing, that is for every element i, we need to iterate through input array in range [i+1, L], this takes O(n ^ 2) time. 

Trying to avoid bruteforcing...

lets say we have an array [7,3,2,8,9]

Why we bruteforce ?

The major reason is we dont know what elements lies after 7, there are various possibilities

1. All the elements after 7 might be less than 7

2. All the elements after 7 might be greater than 7

3. All the elements after 7 might be equal to 7

 The problem is not iterating the array, the problem is doing it from the front. In other words we dont know the future when we start with 7, but if we start from the end we know exactly how many elements lies ahead 7 and how many are greater than 7 and which one is closer

we can create a list of elements which we make sure to maintain in descending order. why maintain descending order ? because for each number we want to know if there are any elements greater than that, if we dont have the descending order then we would need to loop through entire array to pick the one number greater than the current element, then we need to pick the one with minimum index ( we are taking the next greatest element, so we would need to pick the one with min index )

how would that list looks like when we are at 7 ?

[9,8,3,2]

Lets filter all the elements less than 7

[9,8]

Lets pick the element with minimum index

[8]

we pick [8] because that is the element very near to 7, but do we really need to keep 9 in the list ? before we dwell in to that question lets see a chart which represents this value in y-axis

Do we still need 9?

Think about in which case where removing 9 would do harm, that is having 9 not on the list will yield a inconsistent result

lets say we a additional element 10 between 2, 8

 

does it make sense to have the values less than 10 in our list ? in other words in case if we encounter a higher value ( 10 ) and traversing backwards ( 9, 8, 10 ..) could we safely delete the values which are less than that ?

Yes we absolutely can, because 7,3,2 will all choose 10 as the greatest value not 8, not 9.

What we found so far ?

When we encounter a higher element which is greater than all of the elements in the list, then we can safely remove all of the elements in the list which is less than the higher element

Lets just formulate a approach

We will consider this input array [7,3,2,10,8,9]

 

1. we will start from 9, we have an empty list, i.e there are no elements greater than 9 after 9, so we will set answer to element to zero

 

 

 

and we add 9 to the list

 

2. we move to 8, the first element of our list is 9 which is greater than 8, we dont need to do any thing, we will just add 8 to our list

 

3. now we encounter 10, we will remove all elements from list which is less than 10, we will now add 10 to list

 

we could now translate this in to code

 

```

stack = []

for i in range(LEN-1, -1, -1):

  while stack and stack[-1] < nums[i]:

     stack.pop()

  if not stack:

    ans[i] = 0 # lets check if there are any elements

    stack.append(nums[i]) # add current element to stack

  else:

    ans[i] = stack[-1] # use the first element on list.

    stack.append(nums[i])

```

This does the complete process, it keeps a monotonic decreasing stack and compute the greater elements using just O(n) time and using O(n) space