`Given a list, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in list.`

Elements for which no greater element exist, consider next greater element as -1.

`Assume last element of list is -1`

`Lets define function f(i) which will give the next higher of element at index i`

`Then we can define f(i) as`

`f(i) = i + 1, if l[i+1] > l [i]`

`f(i) = f(j), i + 1 <= j < n`

` `

`Solution: `

def nextHigher(l):

higher = {}

ln = len(l) - 1

higher[l[ln]] = -1 # last element of the list

for i in range(ln - 1, -1, -1): #start from the last two element of the list

c, n = l[i] , l[i+1]

if c >= n:

n = higher[n]

while n != -1 and n < c: #iterate through higher till find or

n = higher[n] #end of linked list(-1)

higher[c] = n

return higher

l = [13, 7, 6, 12, 14, 5, 20, 30]

print nextHigher(l)

Advertisements

can you please explain it.