Java-8 solution

public static int minimumLoss(List prices) { int n = prices.size(); Map indexMap = new HashMap<>(); for (int i = 0; i < n; i++) { indexMap.put(prices.get(i), i); }

List<Long> sorted = new ArrayList<>(prices);
Collections.sort(sorted, Collections.reverseOrder());

long minLoss = Long.MAX_VALUE;
for (int i = 0; i < n - 1; i++) {
    long higher = sorted.get(i);
    long lower = sorted.get(i + 1);
    if (indexMap.get(higher) < indexMap.get(lower)) {
        minLoss = Math.min(minLoss, higher - lower);
    }
}

return (int) minLoss;

}

My Python 3 code with a customized binary search tree. Passed all the tess. I know in the worst case, this is O(n^2). But in most cases, it is like O(n log n), if the tree is somewhat balanced.

class Node: def init(self, key): self.left = None self.right = None self.val = key

def minimumLoss(price): # Write your code here

min_loss = float('inf')

root = Node(price[0])
prev = root

for p in price:

    current = root

    while True:

        if current is None:
            if p > prev.val:
                prev.right = Node(p)
                break
            elif p < prev.val:
                prev.left = Node(p)
                break
        elif current.val == p:
            break
        elif current.val < p:
            prev = current
            current = current.right
        elif current.val > p:
            prev = current
            min_loss = min(min_loss, current.val - p)
                                            current = current.left

return min_loss    

!/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

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