Sort by

recency

|

395 Discussions

|

  • + 0 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:

    1. 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.

    2. 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

  • + 1 comment
    def minimumLoss(price):
        # Write your code here
        n = len(price)
        temp = {}
        for i in range(n):
            temp[price[i]] = i
            
            
        sorted_prices = sorted(price)
        minimum_loss = None
        for i in range(n-1):
            if temp[sorted_prices[i+1]] < temp[sorted_prices[i]]:
                loss = sorted_prices[i + 1] - sorted_prices[i]
                if not minimum_loss or loss < minimum_loss:
                    minimum_loss = loss
        return minimum_loss
    
  • + 0 comments

    When you need to sort the data but keep track of the original index positions, use a pair-index structure. In the code below, the 'quickSort()` routine sorts by price in non-increasing order and for elements that have have the same price, it sorts by index in increasing order.

    typedef struct {
        long long price;
        int index;
    } Pair;
    
    void quickSort(void **a, int lo, int hi);
    
    int minimumLoss(long long* price, int n) {
        long long minLoss = 1e16;
        Pair *pair[n], p[n];
        for (int i = 0; i < n; ++i) {
            pair[i] = &p[i];
            p[i].price = price[i];
            p[i].index = i;
        }
        quickSort((void**) pair, 0, n-1);
        for (int i = 0; i < n-1; ++i) {
            if (pair[i]->index > pair[i+1]->index) continue;
            long long loss = pair[i]->price - pair[i+1]->price;
            if (loss < minLoss) minLoss = loss;
        }
        return minLoss;
    }
    
  • + 0 comments

    Java solution with TreeSet that provides a higher function to query the closest higher element.

        public static int minimumLoss(List<Long> prices) {
            var sortedPrices = new TreeSet<Long>();
            var minimumLoss = (long) Integer.MAX_VALUE;
            for (var price : prices) {
                var higher = sortedPrices.higher(price);
                if (higher != null) {
                    minimumLoss = Math.min(minimumLoss, higher - price);
                }
                sortedPrices.add(price);
            }
            return (int) minimumLoss;
        }
    
  • + 0 comments

    def minimumLoss(price): valores = []
    for pv in range(len(price)): for pi in range(pv + 1, len(price)): rest = price[pv] - price[pi] if rest > 0: valores.append(rest)

    return min(valores)