121.Best_Time_to_Buy_and_Sell_Stock_(Easy).md

121. Best Time to Buy and Sell Stock (Easy)

Update: Jun 2, 2024, 18:04 (EST)

Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Question:

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.

Edge Case:

Input: prices = [1,2,0,2]

Output: 2

Walk-through:

Each time we loop over prices[], we can either update mini or maxi, if prices[i] < mini, we update mini, otherwise, we update maxi = prices[i], when we update maxi, we can also update ans.

Note: we can't say elif prices[i] > maxi, because if we change mini to a lower value, and we encounter prices[i] = maxi, we will not be able to update ans, which leads to higher value. (Edge Case)

Python Solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Intialize min = inf, max = 0, check if prices[i] < min, if so, update min. Otherwise, update max and ans = max(ans, max-min)

        # TC: O(n), n=len(prices), SC: O(1)
        mini, maxi = float("inf"), 0
        ans = 0
        for i in range(len(prices)):
            if prices[i] < mini:
                mini = prices[i]
            else:
                maxi = prices[i]
                ans = max(ans, maxi - mini)
        return ans

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Java

class Solution {
    public int maxProfit(int[] prices) {
        /* 
        Use maxi and mini to keep track, if prices[i] < mini, update mini. Else, update maxi = prices[i] and update ans = max(ans, maxi-mini)
        TC :O(n), SC: O(1)
        */
        int maxi = Integer.MIN_VALUE;
        int mini = Integer.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            int price = prices[i];
            if (price < mini) {
                mini = price;
            } else {
                maxi = price;
                ans = Math.max(ans, maxi - mini);
            }
        }
        return ans;
    }
}