We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
defriddle(arr):# tracking indexi=0# stack for indicesstack=[]# results pre-filled with 0sresult=[0]*len(arr)# iterate through arr (but don't stop until stack is empty)whilei<len(arr)orstack:# if stack is empty# or current item (is in bounds of arr and) is greater than or equal to top of stack# then add current item to stackifnotstackor(i<len(arr)andarr[stack[-1]]<=arr[i]):stack.append(i)i+=1continue# at this point, i is the right boundary for a localized minimum# so, we only need to find the left boundary# get localized minimumtop=stack.pop()# calculate width between boundaries# this is i minus previous item in stack# (or the existing length so far if nothing left in stack)# (we subtract 1 for sake of 0-based indices)idx=(i-stack[-1]-1ifstackelsei)-1# set the localized minimum to the calculated width# (but only if it is more than the existing minimum)result[idx]=max(result[idx],arr[top])# now that we have the results prefilled with max minimums# we just need to fill and adjust# iterate backwards through results (skipping last index)foriinrange(len(result)-2,-1,-1):# if the window doesn't have a max# (this is b/c we have only filled those that a number is a minimum of)# or the max of the width is too small# (this can happen b/c we filled in every localized window found,# but not necessarily the max)# then use the previous (i+1) maxifresult[i]==0orresult[i+1]>result[i]:result[i]=result[i+1]returnresult
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Min Max Riddle
You are viewing a single comment's thread. Return to all comments →