Leetcode — Top Interview 150–121. Best Time to Buy and Sell Stock

It’s an easy problem with the description being:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 104

At first you would think about sorting and getting smaller and bigger numbers, but could be that from the array you may get different ranges or numbers before and after that would cause the difference to not match what’s expected, so forget about sorting.

A good way to solve in this case is to consider the min and max and the difference while iterating the array. If the minimum is less than expected, reset everything, otherwise just keep going and update max when less than the max, and always get diff, not just the max, otherwise you may fail when we get less minimum, but not a big max number.

class Solution {
    public int maxProfit(int[] prices) {

        int min = prices[0];
        int max = prices[0];
        int diff = 0;

        for(int i=1;i<prices.length;i++) {
            if(min > prices[i]){
                min = prices[i];
                max = prices[i];
            } else if (max < prices[i]) {
                max = prices[i];
            }

            if(diff < (max - min)) {
                diff = max - min;
            }
        }

        return diff;
    }
}

Runtime: 2 ms, faster than 77.66% of Java online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 61.4 MB, less than 80.34% of Java online submissions for Best Time to Buy and Sell Stock.

You can still improve further removing min and using only max, but the difference is not big a deal, but nonetheless is a performance improvement.

—

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)