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.
It take me some time to find the solution and why the solution is correct.
The solution is very simple, just sort the array with index and then compare the element in the sorted array with its previous neighbors.
The time complexity is nlog(n) governed by the sort.
Why it works?
You first sort the array, and each element has one big brother that is bigger than you(except for the last of course). Imagine you back to the original price array and you are the min price. Your next bigger brother may be on your left and may be on your right.
If on the left, then you can update the minCost, which is the silly investment want. You are wasted and now only need to care about your brothers. Because all your brother is bigger than you, no other brother can skip a brother and minus you to update the minCost.
If on the right, what should we do? Do you need to remember the two prices for further check? You don't know. Ok, let's check the third element.
* It could be like in front of all: [C,.. A,..., B], but C-A>C-B, you don't need to care about A. So check C-B only
* it could be in the middle [A,...C,...,B] you only need to check C-B vs minCost, nothing to do with A.
* it also could be at the back[A...,B...,C]. You can do nothing.
For each case, you find comparing the B,C is the only valid way to generate the minCost.
Hope you can prove that using math induction.
Also,hope that make sense.
defminimumLoss(price):# Write your code heresortedPrice=sorted([(p,idx)foridx,pinenumerate(price)])minLoss=math.infn=len(sortedPrice)foriinrange(1,n):ifsortedPrice[i][1]<sortedPrice[i-1][1]:minLoss=min(minLoss,sortedPrice[i][0]-sortedPrice[i-1][0])returnminLoss
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 →
It take me some time to find the solution and why the solution is correct.
The solution is very simple, just sort the array with index and then compare the element in the sorted array with its previous neighbors. The time complexity is nlog(n) governed by the sort.
Why it works?
You first sort the array, and each element has one big brother that is bigger than you(except for the last of course). Imagine you back to the original price array and you are the min price. Your next bigger brother may be on your left and may be on your right.
If on the left, then you can update the minCost, which is the silly investment want. You are wasted and now only need to care about your brothers. Because all your brother is bigger than you, no other brother can skip a brother and minus you to update the minCost.
If on the right, what should we do? Do you need to remember the two prices for further check? You don't know. Ok, let's check the third element.
* It could be like in front of all: [C,.. A,..., B], but C-A>C-B, you don't need to care about A. So check C-B only
* it could be in the middle [A,...C,...,B] you only need to check C-B vs minCost, nothing to do with A.
* it also could be at the back[A...,B...,C]. You can do nothing.
For each case, you find comparing the B,C is the only valid way to generate the minCost.
Hope you can prove that using math induction.
Also,hope that make sense.