Stock best buy & sell time

Given an array stockPricesYesterday where the keys are the number of minutes into the day (starting with midnight) and the values are the price of Apple stock at that time (e.g. the stock cost $500 at 1am, so stockPricesYesterday[60] = 500).
Write an efficient algorithm for computing the best profit I could have made from 1 purchase and 1 sale of an Apple stock yesterday.
Related image

Approach

We will Iterate through the array while maintaining best sell time, best buy time, best profit and the lowest price. The best sell time is based on the currently known sell time that yields the best profit. .
Every iteration, we calculate profit using the lowest price, if the profit is bigger than the last known best profit, we update the best sell time (using time of current iteration), and best buy time (using the time of the lowest price).

Tests

public class BestProfitCalculatorTest {
    @Test
    public void getBestProfit_bestBuyTimeChanged() throws Exception {
        final StockInfo[] stockPricesYesterday = new StockInfo[]{
                new StockInfo(0, 10),
                new StockInfo(30, 500),
                new StockInfo(60, 5),
                new StockInfo(90, 6),
                new StockInfo(120, 500),
                new StockInfo(150, 10)
        };
        final SellBuyDetails bestProfit = BestProfitCalculator.getBestProfit(stockPricesYesterday);

        assertEquals(bestProfit.buyTime, 60);
        assertEquals(bestProfit.sellTime, 120);
    }

    @Test
    public void getBestProfit_bestSellTimeChanged() throws Exception {
        final StockInfo[] stockPricesYesterday = new StockInfo[]{
                new StockInfo(0, 10),
                new StockInfo(30, 15),
                new StockInfo(60, 400),
                new StockInfo(90, 500),
        };
        final SellBuyDetails bestProfit = BestProfitCalculator.getBestProfit(stockPricesYesterday);

        assertEquals(bestProfit.buyTime, 0);
        assertEquals(bestProfit.sellTime, 90);
    }

    @Test
    public void getBestProfit_bestBuyTimeChanged_bestSellTimeChanged() throws Exception {
        final StockInfo[] stockPricesYesterday = new StockInfo[]{
                new StockInfo(0, 10),
                new StockInfo(30, 15),
                new StockInfo(60, 400),
                new StockInfo(90, 0),
                new StockInfo(120, 500),
        };
        final SellBuyDetails bestProfit = BestProfitCalculator.getBestProfit(stockPricesYesterday);

        assertEquals(bestProfit.buyTime, 90);
        assertEquals(bestProfit.sellTime, 120);
    }

    @Test
    public void getBestProfit_emptyInput_nulloutput() throws Exception {
        final StockInfo[] stockPricesYesterday = new StockInfo[]{
        };
        final SellBuyDetails bestProfit = BestProfitCalculator.getBestProfit(stockPricesYesterday);

        assertNull(bestProfit);
    }

    @Test
    public void getBestProfit_singleitem() throws Exception {
        final StockInfo[] stockPricesYesterday = new StockInfo[]{
                new StockInfo(0, 10),
        };
        final SellBuyDetails bestProfit = BestProfitCalculator.getBestProfit(stockPricesYesterday);

        assertEquals(bestProfit.buyTime, 0);
        assertEquals(bestProfit.sellTime, 0);
    }
}

Solution

class BestProfitCalculator {
    public static SellBuyDetails getBestProfit(StockInfo[] stockPricesYesterday)
    {
        if (stockPricesYesterday.length == 0){
            return null;// todo: throw error
        }

        StockInfo candidate = stockPricesYesterday[0];
        int bestProfit = Integer.MIN_VALUE;
        int bestSellTime = candidate.minutesIntoTheDay;
        int bestBuyTIme = candidate.minutesIntoTheDay;

        for (int i = 1; i < stockPricesYesterday.length; i++) {
            StockInfo stockInfo = stockPricesYesterday[i];

            if (stockInfo.stockPrice < candidate.stockPrice)
            {
                candidate = stockInfo;
            }

            int newPossibleProfit = stockInfo.stockPrice - candidate.stockPrice;
            if (newPossibleProfit > bestProfit)
            {
                bestProfit = newPossibleProfit;
                bestBuyTIme = candidate.minutesIntoTheDay;
                bestSellTime = stockInfo.minutesIntoTheDay;
            }
        }

        return new SellBuyDetails(bestBuyTIme, bestSellTime);
    }
}
public class StockInfo{
    int minutesIntoTheDay;
    int stockPrice;

    public StockInfo(int minutesIntoTheDay, int stockPrice) {
        this.minutesIntoTheDay = minutesIntoTheDay;
        this.stockPrice = stockPrice;
    }
}
public class SellBuyDetails {
    int buyTime;
    int sellTime;

    public SellBuyDetails(int purchuseTime, int sellTime) {
        this.buyTime = purchuseTime;
        this.sellTime = sellTime;
    }
}

Comments