Blind 75 - problem 2 : Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode Solution (C++)

Problem Statement

You are given an array prices where prices[i] represents the stock price on the i-th day.
You want to maximize your profit by choosing a single day to buy and a different day in the future to sell.
Return the maximum profit you can achieve. If you cannot make any profit, return 0.

Example 1:

Input:

prices = [7,1,5,3,6,4]

Output:

5

Explanation:

• Buy on day 1 (price = 1).
• Sell on day 4 (price = 6).
• Profit = 6 - 1 = 5.

---

Example 2:

Input:

prices = [7,6,4,3,1]

Output:

0

Explanation:

• No profitable transaction possible.
• Return 0.

---

Optimal Approach: Sliding Window / Two Pointers

Idea:

Instead of checking every pair of days (brute force), we keep track of the minimum price seen so far and calculate the profit at each step.

Algorithm:

1. Initialize minPrice to a very large number (INT_MAX).
2. Iterate through prices:
   • If prices[i] < minPrice, update minPrice.
   • Otherwise, compute profit = prices[i] - minPrice and update maxProfit.
3. Return maxProfit at the end.

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX; // Store minimum price seen so far
        int maxProfit = 0; // Store maximum profit

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price; // Update minPrice if we find a lower price
            } else {
                maxProfit = max(maxProfit, price - minPrice); // Calculate profit and update maxProfit
            }
        }

        return maxProfit;
    }
};

✅ This solution is 100% submittable on LeetCode.

---

Step-by-Step Execution (Dry Run)

Input:

prices = [7, 1, 5, 3, 6, 4]

Day	Price	Min Price (So Far)	Profit (price - minPrice)	Max Profit
0	7	7	0	0
1	1	1	0	0
2	5	1	4	4
3	3	1	2	4
4	6	1	5	5
5	4	1	3	5

Final Output: 5

---

Alternative Approaches

1. Brute Force (Nested Loops)

• Check all pairs (i, j) where i < j and compute profit.
• Time Complexity: O(N²) (Very slow).
• Space Complexity: O(1).
• 🚫 Not optimal for large inputs.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.size(); i++) {
            for (int j = i + 1; j < prices.size(); j++) {
                maxProfit = max(maxProfit, prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
};

---

2. Dynamic Programming (DP)

• Maintain an array dp[i] to store max profit at each step.
• Time Complexity: O(N).
• Space Complexity: O(N) (Extra array).

🚫 Uses extra space, so not the best choice.

---

Best Approach: Two Pointers / Sliding Window

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Brute Force	O(N²)	O(1)	Too slow for large N.
Dynamic Programming	O(N)	O(N)	Extra space used.
Sliding Window (Two Pointers)	✅ O(N)	✅ O(1)	Best balance of speed & memory.

---

Time and Space Complexity

✅ Sliding Window Approach:

• Time Complexity: O(N) (Single pass through prices).
• Space Complexity: O(1) (No extra storage used).

---

Conclusion

• Best approach: Sliding Window / Two Pointers
• Key takeaway: Track minPrice and compute profit at each step.
• Why it’s best: Runs in O(N) with constant space.

---

More Problems to Practice

1. Best Time to Buy and Sell Stock II
2. Best Time to Buy and Sell Stock III
3. Best Time to Buy and Sell Stock with Cooldown
4. Maximum Subarray (Kadane’s Algorithm)

🔥 Keep practicing, and you’ll master coding interviews in no time! 🚀