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. Prepare
  2. Algorithms
  3. Search
  4. Minimum Loss
  5. Discussions

Minimum Loss

Sort by

recency

|

398 Discussions

|

  • 2k23_cscys231101
     + 0 comments

    !/bin/python3

    import math import os import random import re import sys

    def minimumLoss(price): n = len(price) # Create a dictionary of price to year index price_index = {p: i for i, p in enumerate(price)}

    # Sort prices ascendingly
sorted_prices = sorted(price)

min_loss = float('inf')

# Check adjacent prices in sorted list
for i in range(1, n):
    high = sorted_prices[i]
    low = sorted_prices[i - 1]

    # Buy (high price) must be before sell (low price)
    if price_index[high] < price_index[low]:
        min_loss = min(min_loss, high - low)

return min_loss

  • Manjulpandey17
     + 0 comments

    def minimumLoss(price): indexed_prices = [(p, i) for i, p in enumerate(price)] indexed_prices.sort(key=lambda x: x[0]) # sort by price

    min_loss = float('inf')

for i in range(len(indexed_prices) - 1):
    lower_price, lower_index = indexed_prices[i]
    higher_price, higher_index = indexed_prices[i + 1]

    # buy at lower price year, sell at higher price year (buy_index < sell_index)
    # so loss is positive
    if lower_index > higher_index:
        loss = higher_price - lower_price
        if loss < min_loss:
            min_loss = loss

return min_loss

    if name == "main": n = int(input()) price = list(map(int, input().split())) print(minimumLoss(price))

  • abhiram_kankipa1
     + 0 comments
    def minimumLoss(price):
    # Write your code here
    p_dict ={}
    p_len=len(price)
    for i in range(p_len):
        p_dict[price[i]]=i
    price.sort()
    min_diff=price[1]-price[0]
    if p_len ==2:
        return min_diff
    for i in range(2,p_len):
        
        if price[i]-price[i-1]<min_diff \
            and p_dict[price[i]]< \
            p_dict[price[i-1]]:
            min_diff = price[i]-price[i-1]
    return min_diff

  • sammy27berger
     + 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

  • afzal_saiyed931
     + 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