# Minimum Loss

See the original problem on HackerRank.

## Solutions

The naive solution is quadratic and it’s too slow for a few test cases. We show it here, for completeness:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  #include #include #include #include #include using namespace std; int main() { int n; cin >> n; vector v(n); copy_n(istream_iterator(cin), n, begin(v)); auto minLoss = INT_MAX; for (auto i=0; i v[j]) { minLoss = min(minLoss, v[i] - v[j]); } } } cout << minLoss; } 

### Set-based solution

We need to amortize the internal loop.

Suppose we process the elements in an online fashion (e.g. in streaming). The elements already processed constitute the “history” of our data. For the next element $$p$$, we need to search the “history” for the first element greater than $$p$$.

If our history is sorted, we can easily answer to the query with a binary search (or such). This is known as lower bound.

Thus, we can use a sorted data structure supporting such an operation.

In C++ we can use a std::set:

  1 2 3 4 5 6 7 8 9 10 11  int N; cin >> N; price i, loss = numeric_limits::max(); set prices; while (cin >> i) { const auto lb = prices.lower_bound(i); // 👈💣 prices.insert(lb, i); if (lb != end(prices)) loss = min(loss, *lb-i); } cout << loss; 

In Java we can use a TreeSet:

  1 2 3 4 5 6 7 8 9 10 11 12 13  Scanner in = new Scanner(System.in); TreeSet prices = new TreeSet(); int loss = Integer.MAX_VALUE; while (in.hasNext()) { int elem = in.nextLong(); Integer ub = prices.higher(elem); // 👈💣 if (ub != null) loss = Math.min(loss, ub-elem); prices.add(elem); } System.out.println(loss); in.close();

In C# we can use SortedSet, left as an exercise.

The cost of this solution is $$O(N \cdot logN)$$.

What happens if duplicates kick in and 0 is not admitted as minimum loss?

We should replace lower bound with upper bound, to skip the duplicates.

## Sort-based solution

Even more efficient is to preprocess data.

Intuition: if the prices are sorted, the minimum loss is given by two adjacent prices. We just need to check if the pair is “valid”, that is: if the sell price is actually following the purchase (the sell is in the future).

Thus, we can duplicate our data and add an index for each price. The index is ascending and it just represents then history.

For example, for: 14 7 8 2 5

We have:

(0, 14) (1, 7) (2, 8) (3, 2) (4, 5)

Now we can sort the data and the history won’t be lost:

(3, 2) (4, 5) (1, 7) (2, 8) (0, 14)

We can finally process adjacent pairs. Since we sell at a loss:

• the right pair (price is bigger) represents the purchase price
• the left pair (price is lower) represents the sell price

We only need to wipe out pairs that are not admittable, that is purchase happens after the sell.

For example, (3, 2) and (4, 5) must be discarded because purchase (4, 5) happens after the sell (3, 2), since the position 4 is greater than the position 3.

On the other hand, (4, 5) and (1, 7) are ok because (1, 7) is before (4, 5).

A possible C++ implementation follows:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  int main() { int n; cin >> n; vector> v(n); int idx = 0; // map values to (idx, value) transform( istream_iterator(cin), istream_iterator(), begin(v), [&](auto i){return make_pair(i, idx++);} ); sort(begin(v), end(v)); auto minLoss = numeric_limits::max(); for (auto i=1; i

The solution above is just an application of three patterns: zip | map | reduce.

A picture worth a thousand words:

In C++ this can be implemented in terms of std::inner_product:

 1 2 3 4 5 6 7 8  cout << inner_product(next(begin(v)), end(v), begin(v), numeric_limits::max(), [](auto... m) { return min(m...); }, [](const auto& p1, const auto& p2) { return p1.second < p2.second ? p1.first-p2.first : numeric_limits::max(); }); 

That is not straightforward.

Python is a valuable ally:

 1 2 3 4 5 6 7  index = range(0, len(price)) zipped = zip(price, index) zipped.sort(key = lambda t: t[0]) zipped = izip(zipped, zipped[1::]) valids = ifilter(lambda (x1, x2): x1[1]>x2[1], zipped) differences = imap(lambda (x1, x2) : x2[0]-x1[0], valids) print min(differences)

Or, more pythonic:

 1 2 3 4 5 6  index = range(len(price)) zipped = sorted(zip(price, index), key=lambda x: x[0]) zipped = zip(zipped, zipped[1::]) valids = ((x1, x2) for x1, x2 in zipped if x1[1] > x2[1]) differences = (x2[0] - x1[0] for x1, x2 in valids) print min(differences)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  import Data.List (sortBy) comparePrices (a,_) (b,_) = compare a b validPair ((_, sell), (_, buy)) = buy < sell loss ((sellPrice, _), (buyPrice, _)) = buyPrice - sellPrice main = do _ <- getLine pricesStr <- getLine let prices = read <$> words pricesStr :: [Int] let pricesAndIndexes = zip prices [0..] let sortedByPrice = sortBy comparePrices$ pricesAndIndexes let valids = filter validPair $zip sortedByPrice (tail sortedByPrice) let differences = loss <$> valids print $minimum differences Another haskell version, using list comprehension:   1 2 3 4 5 6 7 8 9 10 11 12 13 14  import Control.Monad (ap) import Data.List (sortOn) minimumLoss xs = minimum [ bPrice - sPrice | ((sPrice, _), (bPrice, _)) <- [ x | x@((_, s), (_, b)) <- ap zip tail$ sortOn fst \$ zip xs [0 ..] , b < s ] ] main = interact (show . minimumLoss . fmap read . tail . words)
 1 2 3 4 5 6 7  def minimumLoss(price: List[Long]): Long = { val priceIndexed = price.zip(price.indices).sortWith(_._1 < _._1) val pairs = priceIndexed.zip(priceIndexed.tail) val validPairs = pairs.filter(p => p._1._2 > p._2._2) val losses = validPairs.map(p => p._2._1 - p._1._1) losses.min }