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.
  1. Minimum Loss 1
  2. Discussions

Minimum Loss 1

Sort by

recency

|

12 Discussions

|

  • gtai_quant
     + 0 comments
    import bisect

def minimumLoss(price):
    min_price = float('inf')
    sorted_price = []
    for num in price:
        idx = bisect.bisect_right(sorted_price, num)
        if idx < len(sorted_price):
            min_price = min(min_price, sorted_price[idx] - num)
        sorted_price.insert(idx, num)
        
    return min_price

  • khiemnd9112
     + 0 comments

    Java8 using TreeMap

    public static int minimumLoss(List<Long> price) {
    // Write your code here
        
        int n = price.size();
        long loss = Integer.MAX_VALUE;
        
        long lastPrice = 0;
        int lastIdx = 0;
        
        TreeMap<Long, Integer> map = new TreeMap<>();
        
        for (int i = 0; i < n; i++) {
            map.put(price.get(i), i);
        }
        
        for (Map.Entry<Long, Integer> e : map.entrySet()) {
            long curPrice = e.getKey();
            int curIdx = e.getValue();
            
            if (curIdx < lastIdx) {
                loss = Math.min(loss, curPrice - lastPrice);
            }
            
            lastPrice = curPrice;
            lastIdx = curIdx;
        }
        
        return (int) loss;
    }

  • robjrm
     + 0 comments

    Since similar solutions rely on either a sorted array or using binary search n times where n is the length of the array, the time complexity comes out to O(nlogn) either way, I figured this is more intuitive:

    def minimumLoss(price):
    # Write your code here
    p_to_i = {}
    for i,p in enumerate(price):
        p_to_i[p] = i
    
    price.sort()
    min_value = math.inf
    for i in range(1,len(price)):
        if p_to_i[price[i-1]] > p_to_i[price[i]]:
            min_value = min(min_value,price[i] - price[i-1])
    return min_value

  • wenyu2
     + 0 comments

    Proof of correctness of looking at min diff of only consecutive numbers (when their positions satisfy the requirement) in a sorted price list: suppose that we have prices p1<p2<p3 where we assume that p1,p3 is the optimal pair. In the original list p1 must appear after p3, and since p1,p2 is not chosen as the optimal pair despite p2-p1<p3-p1, p2 must appear after p1. Then we know that p2 appears after p3 and p3-p2<p3-p1, and we should've chosen p2,p3 instead, contradiction.

  • fukinscud
     + 0 comments
    def minimumLoss(prices):
    from bisect import bisect_left
    
    min_loss = None
    visited = [prices[0]]
    
    for i in range(1, len(prices)):
        price = prices[i]
        j = bisect_left(visited, price)
        visited.insert(j, price)
        if j + 1 == len(visited):
            continue
        loss = visited[j + 1] - visited[j]
        min_loss = min(min_loss, loss) if min_loss else loss
    return min_loss