Solving Coding Problem: Best Time to Buy and Sell Stock

Given an array of integers where the ith integer represents the price of the stock on day i, return the largest possible profit from completing one transaction (i.e. buying 1 share and selling 1 share).
Examples: Given the following prices…

// Buy on day 1 and sell on day 5 for a profit of 5 - 1 = 4. 
prices = [1, 2, 3, 4, 5], return 4. 
// Buy on day 4 and sell on day 9 for a profit of 11 - 1 = 10. 
prices = [4, 5, 2, 1, 6, 10, 4, 9, 11], return 10. 
// Buying and selling the stock at any point would yield a negative profit. 
prices = [33, 18, 8, 2], return 0

You’ve probably heard of the expression “buy low, sell high” and that’s exactly how we’re trying to solve our problem today. Our goal is to find the optimal point to buy (lowest point) and optimal point to sell (highest point after we’ve bought). By finding these two points we can then calculate our profit as follows price we sold at — price we bought at. Let’s first focus on finding the low price. This is as easy as using a for loop and updating a min variable any time the current price is lower than our min.

int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
    // update our min if the current price is smaller than our current min.
    min = Math.min(min, prices[i]);
}

Now that we understand the logic that we can use to find the low price and therefore the price at which we should buy our stock, now we just need to understand when to sell our stock. This can be accomplished by simply checking if our current stock price is greater than our min if it is let’s simulate selling at that point.

int profit = 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    if (prices[i] > min) {
        profit = prices[i] - min;
    }
}

Great now we’re recording our profit! However, because we are always reassigning our profit to the current calculation if the current price is greater than our min, we are not guaranteeing that we always store the largest profit. Now, using our two methods of finding the low price and simulating making transactions, with some slight tweaking, we can guarantee that we always store the max profit!

public int largestProfit(int[] prices) {
    int profit = 0;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < prices.length; i++) {
        if (prices[i] > min) {
            profit = Math.max(profit, prices[i] - min);
        } else {
            min = prices[i];
        }
    }
    return profit;
}

This problem seems complicated, but really just boils down to the code above. Our solution correctly updates a minimum value as necessary while simultaneously simulating making trades for any prices that is greater than our minimum at the time. Now with our changes, we are guaranteeing that we only reassign our profit if it yields a larger value!

# Big-O Analysis
Runtime: O(N) where N is the number of prices.
Space complexity: O(1) as we only need a few variables (regardless of the size of the prices array)