To print immediate Higher of all elements of a list

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

One thought on “To print immediate Higher of all elements of a list

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s