Best Time To Buy And Sell Stock

Return the maximum profit you can achieve from this transaction.

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

• Solution in Java: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/submissions/1208643109/

Time complexity : O(n) Space Complexity : O(1) (As we are only using 2 variables)

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int minPrice = prices[0];

        for(int idx=0;idx<prices.length;idx++)
        {
            profit = Math.max(profit,prices[idx]-minPrice);
            minPrice = Math.min(minPrice,prices[idx]);
        }
        return profit;
    }
}

• Soluton in Python:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        minPrice = prices[0]
        profit = 0
        for price in prices:
            profit = max(profit,price-minPrice)
            minPrice = min(minPrice,price)
        return profit
        

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

• We can also solve this using two pointer approach, Kadanes Algorithm.

class Solution {
    public int maxProfit(int[] prices) {
        int left = 0;
        int right = 1;
        int profit = 0;

        while(right < prices.length)
        {
            if(prices[right] > prices[left])
            {
                profit = Math.max(profit,prices[right] - prices[left]);
            }
            else
            {
                left = right;
            }
            right += 1;
        }
        return profit;
    }
}