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.
Key insight to avoid O(n^2) - after sorting the array, you can be sure that the prices you're looking for are adjacent. We're given that there is a solution - so let's call the 'optimal' buying and selling prices B and S, for **B**uy and **S**ell.
We know B and S is a solution; therefore, pos(B) < pos(S), and B > S.
Now for the sake of contradiction, assume B and S are not adjacent when sorted. Therefore, there must be some value X such that S < X < B. Now let's go back to the original array:
If pos(X) < pos(B), then we could have formed the buy-sell pair of buying at X and selling at S. Because X is closer to S than B is, this would have been a better pair then our 'optimal' pair - a contradiction.
If pos(B) < pos(X), then we could have formed the buy-sell pair of buying at B and selling at X. Because X is closer to B than S is, this would also have been better than our 'optimal' pair - another contradition.
Therefore, we know that B and S must be adjacent when sorted. The remainder of the nlogn algorithm is left as an exercise to the reader XD
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 →
Key insight to avoid O(n^2) - after sorting the array, you can be sure that the prices you're looking for are adjacent. We're given that there is a solution - so let's call the 'optimal' buying and selling prices B and S, for **B**uy and **S**ell.
We know B and S is a solution; therefore, pos(B) < pos(S), and B > S.
Now for the sake of contradiction, assume B and S are not adjacent when sorted. Therefore, there must be some value X such that S < X < B. Now let's go back to the original array:
If pos(X) < pos(B), then we could have formed the buy-sell pair of buying at X and selling at S. Because X is closer to S than B is, this would have been a better pair then our 'optimal' pair - a contradiction.
If pos(B) < pos(X), then we could have formed the buy-sell pair of buying at B and selling at X. Because X is closer to B than S is, this would also have been better than our 'optimal' pair - another contradition.
Therefore, we know that B and S must be adjacent when sorted. The remainder of the nlogn algorithm is left as an exercise to the reader XD