Vansh Aggarwal

Posted on Mar 28

LeetCode Solution: 121. Best Time to Buy and Sell Stock

#leetcode #dsa #programming #tutorial

Mastering LeetCode 121: The Easiest Stock Problem You'll Ever Solve! 💰

Hey there, future coding rockstars! 👋 Vansh here, back with another LeetCode breakdown designed to make you say, "Aha! I got this!" Today, we're diving into a classic problem that's often a gateway to more complex dynamic programming challenges: 121. Best Time to Buy and Sell Stock.

Don't let the "stock market" theme scare you. This problem is super beginner-friendly and perfect for honing your greedy algorithm skills. Let's make some virtual profit!

The Problem: When to Buy, When to Sell? 📈

You're given an array called prices, where prices[i] represents the price of a stock on the i-th day. Your mission, should you choose to accept it, is to figure out how to maximize your profit.

Here's the catch:

You can only perform one transaction: buy one stock, then sell it later.
You must buy before you sell. No time travel allowed!
If you can't make any profit (meaning all prices after your buy day are lower), you should return 0.

Let's look at an example to make it crystal clear:

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

If you buy on Day 1 (price = 7) and sell on Day 2 (price = 1), you lose money (-6). Bad deal!
If you buy on Day 2 (price = 1) and sell on Day 3 (price = 5), profit = 4. Better!
If you buy on Day 2 (price = 1) and sell on Day 5 (price = 6), profit = 5. This is our maximum!

Example 2:
prices = [7, 6, 4, 3, 1]

In this depressing scenario, the price just keeps dropping. No matter when you buy, any future selling day will result in a loss. So, the maximum profit here is 0. You simply choose not to make a transaction.

The Intuition: Always Look for a Bargain! 👀

Imagine you're actually trying to buy and sell stocks in real life, but with a super power: you know all future prices. (If only, right? 😉)

To maximize profit, what's your ultimate goal?

Buy low.
Sell high.

Since you can only make one transaction, you need to find the absolute lowest price you could have bought at before a specific day, and then see if selling on that specific day gives you the biggest profit.

So, as you go through the days (prices), you'll always want to keep track of:

What's the lowest price I've seen so far up to this point? (This is your potential 'buy' price).
What's the maximum profit I've managed to make by selling on the current day, assuming I bought at that 'lowest price seen so far'?

This thought process leads us to a simple, yet powerful, "greedy" approach!

The Approach: One Pass to Riches! 🏃‍♂️

Let's formalize our intuition into a step-by-step plan:

Initialize max_profit: We'll start with 0, because if we can't make any profit, we'll return 0.
Initialize min_price: We need to keep track of the lowest price encountered so far. A good starting point would be the price on the first day (prices[0]), or an extremely large number (like INT_MAX in C++). Since the constraints say prices.length >= 1, prices[0] is safe.
Iterate through the prices array: Go through each day's price, starting from the very beginning.
- Update min_price: For each prices[i], compare it with your current min_price. If prices[i] is lower, update min_price to prices[i]. This ensures min_price always holds the lowest buying opportunity up to the current day.
- Calculate potential profit: The profit if you sell today (prices[i]) would be prices[i] - min_price.
- Update max_profit: Compare this potential_profit with your max_profit recorded so far. If the potential_profit is greater, update max_profit.
Return max_profit: After checking all days, max_profit will hold the highest profit you could achieve.

This single pass guarantees that for every potential selling day i, min_price correctly represents the lowest price on any day j where j <= i. Since we must buy before we sell, this min_price is always a valid buy point.

The Code: Simple and Sweet! ✨

#include <vector>
#include <algorithm> // Required for std::min and std::max

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        // Initialize max_profit to 0, as no transaction means 0 profit.
        int max_profit = 0;

        // Initialize min_price with the price on the first day.
        // We assume prices.length >= 1 based on constraints.
        int min_price = prices[0];

        // Iterate through all prices to find the best buy and sell points.
        for (int i = 0; i < prices.size(); ++i) {
            // Step 1: Update the minimum price encountered so far.
            // If the current price is lower than our recorded min_price, update it.
            min_price = std::min(min_price, prices[i]);

            // Step 2: Calculate the potential profit if we sell on the current day (prices[i]).
            // This profit is prices[i] minus the lowest price seen so far (min_price).
            int current_profit = prices[i] - min_price;

            // Step 3: Update the overall maximum profit.
            // If the current_profit is greater than our recorded max_profit, update it.
            max_profit = std::max(max_profit, current_profit);
        }

        // After iterating through all days, max_profit holds the maximum possible profit.
        return max_profit;
    }
};

Wait, a quick note on the original code snippet! The snippet provided had a small logical error where the res = max(...) line was outside the loop. The corrected code above properly integrates this logic inside the loop, ensuring we calculate potential profit for each day using the minimum price up to that day. This is crucial for correctness!

Complexity Analysis: How Efficient Is It? 🚀

Let's break down the efficiency of our solution:

Time Complexity: O(N)
- We iterate through the prices array exactly once.
- Inside the loop, we perform a constant number of operations (comparisons, subtractions, assignments).
- Therefore, the time taken grows linearly with the number of days (N) in the prices array. This is as efficient as it gets for this problem!
Space Complexity: O(1)
- We only use a few extra variables (max_profit, min_price, current_profit) to store our state.
- The amount of extra memory used does not depend on the size of the input array. It remains constant.

This is a highly optimized solution – both time and space efficient!

Key Takeaways: What Did We Learn? 🧠

Greedy is Gold (Sometimes!): For problems where you need to make the "best" choice at each step to reach an optimal global solution, a greedy approach can be incredibly effective. Here, always tracking the min_price and maximizing profit locally leads to the global maximum.
Single Pass Power: Many problems can be solved efficiently by iterating through the data just once, updating state variables as you go.
Think about "So Far": When dealing with sequences or arrays, keeping track of the minimum/maximum/sum "so far" is a common and powerful pattern.

This problem is an excellent starting point for understanding how to approach array-based optimization problems. Keep practicing, and you'll be crushing more complex challenges in no time!

Happy coding! ✨

_{Author Account: Vansh2710 | Published: 2026-03-28 22:33:38}

DEV Community