Best Time to Buy and Sell Stock

Given an array where prices[i] represents the stock price on the i-th day, find the maximum profit you can achieve by buying once and selling once in the future.

Example:

Input:  [7,1,5,3,6,4]
Output: 5

Explanation:

Buy at 1
Sell at 6

Profit = 6 - 1 = 5

---

My First Thought (Brute Force)

For every day, I can assume it is the buying day.

Then I can check every future day as a potential selling day and calculate the profit.

Finally, I'll keep track of the maximum profit seen so far.

Brute Force Code

class Solution {
    public int maxProfit(int[] prices) {

        int maxProfit = 0;

        for (int buy = 0; buy < prices.length; buy++) {

            for (int sell = buy + 1; sell < prices.length; sell++) {

                int profit = prices[sell] - prices[buy];

                maxProfit = Math.max(maxProfit, profit);
            }
        }

        return maxProfit;
    }
}

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

While this works, we're checking many unnecessary buy-sell combinations.

---

The Key Observation

Let's look at:

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

When I reach a particular day, I don't actually care about all previous prices.

I only care about:

The minimum stock price seen so far.

For example:

Current Price = 6
Minimum Price Seen = 1

Profit = 6 - 1 = 5

To maximize profit at any day:

Profit = Current Price - Minimum Price Seen So Far

This means we don't need nested loops.

We just need to keep track of the cheapest buying opportunity encountered so far.

---

A DP Thought I Had

Initially, I thought about creating:

dp[i] = Maximum profit till index i

Something like:

dp[i] = Math.max(
    dp[i - 1],
    prices[i] - minPriceTillNow
);

But after thinking deeper, I realized that the most important information isn't the previous profit.

It's actually:

Minimum price seen so far

Since only the minimum value matters, the DP array can be compressed into just two variables.

This makes the problem more of a Prefix Minimum pattern than a Dynamic Programming problem.

---

Optimal Solution

Maintain:

minPrice  -> cheapest stock seen so far
maxProfit -> best answer so far

For every day:

1. Calculate profit using the current price.
2. Update the answer.
3. Update the minimum price seen so far.

Optimal Code

class Solution {
    public int maxProfit(int[] prices) {

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {

            int profit = prices[i] - minPrice;

            maxProfit = Math.max(maxProfit, profit);

            minPrice = Math.min(minPrice, prices[i]);
        }

        return maxProfit;
    }
}

Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

---

Quick Dry Run

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

Price	Min Price	Profit	Max Profit
7	7	0	0
1	1	0	0
5	1	4	4
3	1	2	4
6	1	5	5
4	1	3	5

Answer:

5

---

What I Learned

Whenever I see:

• Maximum profit
• Maximum difference
• Best future outcome based on past values

I should ask:

Can I maintain a running minimum or maximum while traversing?

This simple pattern can turn an O(N²) solution into an O(N) solution.

---

I'm currently solving the Striver SDE Sheet Challenge and documenting my learnings, patterns, mistakes, and interview insights along the way.

LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
X (Twitter): https://x.com/Jaspree54799902
GitHub: https://github.com/codewithjaspreet