algoadvance

Leetcode 121. Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th 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: [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.

2. Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done, so the maximum profit is 0.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Clarifying Questions

1. Q: Can we buy and sell the stock on the same day? A: No, we must buy on one day and sell on a different day in the future.

2. Q: What do we return if there is no way to achieve a profit? A: Return 0.

3. Q: Is it guaranteed that prices will not be empty? A: Yes, as per the constraints, prices.length is at least 1.

Strategy

1. Initialize Variables: Create two variables, minPrice to keep track of the minimum price encountered so far, and maxProfit to store the maximum profit found.

2. Iterate Over Prices: Loop through each price in the array:
   • Update minPrice to be the minimum of minPrice and the current price (this ensures we always buy at the lowest possible price up to the current day).
   • Calculate the potential profit if sold at the current price (current price - minPrice).
   • Update maxProfit to be the maximum of maxProfit and the potential profit calculated.
3. Return Result: After iterating through the array, return maxProfit.

Code

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) {
            return 0;
        }
        
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for(int price : prices) {
            if(price < minPrice) {
                minPrice = price;
            } else if(price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        
        return maxProfit;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of days (length of the prices array). This is because we traverse the list of prices once.
• Space Complexity: O(1), as we are using a constant amount of additional space regardless of the input size.

This approach ensures we get the maximum profit possible by keeping track of the lowest price to buy and the highest potential profit at each step.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?