121. Best Time to Buy and Sell Stock

Given an array prices where prices[i] is the price of a given stock on the ith day. Return the maximum profit that can be achieved by buying on one day and selling on another.

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.

---

Intuition

• To identify the max profit, we need to buy on the day when price is lowest & sell on the day its highest till the day i.

Approach

• Iterate over the array store the minPrice & maxPrice seen till now.

• If we have to change the minPrice it mean we are buying on that day so maxPrice also needs to be reset.

Complexity

• Time complexity : $\text{O}(n)$

  • We iterate over the prices only once.

• Space complexity : $\text{O}(1)$

  • There is no extra space needed.

Code

public int maxProfit(int[] prices) {
	int minPrice = Integer.MAX_VALUE, maxPrice = Integer.MIN_VALUE,maxProfitTillNow = 0;

	for (int i = 0; i < prices.length; ++i) {
		// If current day price is the lowest 
		// reset the maxPrice also as it means we are buying on current day
		if(prices[i] < minPrice ) {
			minPrice = prices[i];
			maxPrice = prices[i];
		} else {
			// Update the maxPrice by comparing price with current day price
			maxPrice = Math.max(maxPrice,prices[i]);
		
			// Recalculate the max profit we can achieve till date
			maxProfitTillNow = Math.max(maxProfitTillNow,maxPrice-minPrice);
		}
	}
  
return Math.max(maxProfitTillNow,maxPrice - minPrice);

}