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.
defminimumLoss(price):# Thinking process:# 1 Brutal force (n^2)# 2 Greedy apporach.(nlogn)# Think about insertion sort. But don't use insertion sort# in one step, after we insert from the current position# to a previously sorted subarray, # for our question,we only need to# compare the current number to the previous number of its inserted pos.# example: input=[5,10,3,4]# insertion sort step 2 # subarray is [10,5] (sort from big to small)# we inserted 3, subarray becomes [10,5,3]. For our question we only need to compare 3 with 5# if there is incoming number such as 4 we only need to compare with# inserted pos([10,5,4,3], insert 4) which is also 5, we don't need to care # about 3, otherwise we will get a positive loss.# after the sort complete, we get our min reslut, and the result must be come from a# sorted array, between a number and its left neighbour.# In conclusion, we only need to compare the neighbour # in an sorted array and we don't # need to use the insertion sort.## question to ask:# Does 0 count as a valid loss?idx2Price=collections.defaultdict(list)foridx,pinenumerate(price):idx2Price[p].append(idx)iflen(idx2Price[p])>1:return0n=len(price)res=math.infprice.sort(reverse=True)foriinrange(1,n):ifidx2Price[price[i]]>idx2Price[price[i-1]]:res=min(res,price[i-1]-price[i])returnres
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Minimum Loss
You are viewing a single comment's thread. Return to all comments →