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 <iterator>
#include <climits>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
auto minLoss = INT_MAX;
for (auto i=0; i<n; ++i)
{
for (auto j=i+1; j<n; ++j)
{
if (v[i] > v[j])
{
minLoss = min(minLoss, v[i]  v[j]);
}
}
}
cout << minLoss;
}

Setbased 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<price>::max();
set<price> prices;
while (cin >> i)
{
const auto lb = prices.lower_bound(i); // 👈💣
prices.insert(lb, i);
if (lb != end(prices))
loss = min(loss, *lbi);
}
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<Integer> prices = new TreeSet<Integer>();
int loss = Integer.MAX_VALUE;
while (in.hasNext())
{
int elem = in.nextLong();
Integer ub = prices.higher(elem); // 👈💣
if (ub != null)
loss = Math.min(loss, ubelem);
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.
Sortbased 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<pair<long long, int>> v(n);
int idx = 0;
// map values to (idx, value)
transform(
istream_iterator<long long>(cin),
istream_iterator<long long>(),
begin(v),
[&](auto i){return make_pair(i, idx++);}
);
sort(begin(v), end(v));
auto minLoss = numeric_limits<long long>::max();
for (auto i=1; i<n; ++i)
{
if (v[i].second < v[i1].second)
{
minLoss = min(v[i].firstv[i1].first, minLoss);
}
}
cout << minLoss;
}

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<long long>::max(),
[](auto... m) { return min(m...); },
[](const auto& p1, const auto& p2) {
return p1.second < p2.second ?
p1.firstp2.first :
numeric_limits<long long>::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)

Haskell:
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)

This solution is faster than the setbased one. Possible cons are:
 it does not work online (it requires preprocessing)
 it requires some extra memory to store the indices
A functional solution in Scala:
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
}
