1. Understand the problem

• Given an array prices where prices[i] is the price of a given stock on day i, find the maximum profit you can achieve by choosing one day to buy and one later day to sell. Return 0 if no profit is possible.

2. Clarifying questions

1. What are valid input sizes?

• A (assume): n can be large (e.g., up to 10^5 or 10^6) — so aim for O(n) time, O(1) extra space if possible

1. Can prices be negative?

• Realistic stock prices are non-negative. But algorithm works if negative values are allowed (profit := sell - buy still valid).

1. What about duplicates / equal adjacent prices?

• Allowed. Buying and selling on same day is not allowed (sell index must be > buy index). If all equal → profit = 0.

1. Q: What if array is empty or length 1? A: Return 0 (no possible buy-sell pair).

3. Work through examples

1. Increasing prices: [1, 2, 3, 4, 5] → buy day 0 at 1, sell day 4 at 5 → profit 4.

2. Decreasing prices: [7, 6, 4, 3, 1] → no profitable trade → 0.

3. Peak in middle: [3, 8, 1, 10] → best: buy at 1 (index 2), sell at 10 (index 3) → profit 9.

4. Negative allowed: [-3, -1, -2, 5] → buy at -3 sell at 5 profit 8 (works).

5. Duplicate prices: [2,2,2,2] → 0.

6. Empty or single: [], [5] → 0.

7. Large fluctuations: [5, 1, 5, 3, 6, 2, 9] → best buy 1 sell 9 profit 8.

4. Brainstorm 2–3 solutions

4.1. Brute force

• Try every pair (i, j) with j > i and compute prices[j] - prices[i]. Track max.

• Time: O(N^2).

• Space: O(1).

4.2. One-pass (keep min price so far)

• Iterate once; maintain min_price seen so far and max_profit:

• For each price p: max_profit = max(max_profit, p - min_price); min_price = min(min_price, p).

• Time: O(n).

• Space: O(1).

4.3. Kadane-like

Idea:

arr = [a, b, c]

c - a = (b - a) + (c - b)

=> Move it to find Kandane maxSumArray problem [b - a, c - b]

• Time: O(n).

• Space: O(1).

4. Sliding Window

• We try to keep track of the lowest buy price (at l)

• And check the potential profit if we sell on day r.

• Time: O(n).

• Space: O(1).

5. Implement solutions

5.1. Brute force

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(len(prices)):
            buy = prices[i]
            for j in range(i + 1, len(prices)):
                sell  = prices[j]
                res = max(res, sell - buy)
        return res

• Time: O(N^2).

• Space: O(1).

5.2. Sliding Window (Two Pointers)

• left: smallest, right: increasement

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r = 0, 1
        maxP = 0

        while r < len(prices):
            if prices[l] < prices[r]:
                profit = prices[r] - prices[l]
                maxP = max(maxP, profit)
            else:
                l = r
            r += 1
        return maxP

• Time: O(N).

• Space: O(1).

5.3. Kandane Algorithm

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        max_profit = 0
        current_sum = 0

        for i in range(1, len(prices)):
            diff = prices[i] - prices[i - 1]
            current_sum = max(0, current_sum + diff)
            max_profit = max(max_profit, current_sum)

        return max_profit

• Idea: c - a = (b - a) + (c - b)

• Time: O(N).

• Space: O(1).

5.4. Dynamic Programming

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxP = 0
        minBuy = prices[0]

        for sell in prices:
            maxP = max(maxP, sell - minBuy)
            minBuy = min(minBuy, sell)
        return maxP

• Time: O(N).

• Space: O(1).

6. Run the testcase

diff = [1-7, 5-1, 3-5, 6-3, 4-6]
diff = [-6, +4, -2, +3, -2]

i	diff[i]	current_sum before	current_sum after	max_profit	Note
1	-6	0	max(0, 0-6)=0	0	reset (loss)
2	+4	0	max(0, 0+4)=4	4	new profit streak
3	-2	4	max(0, 4-2)=2	4	small dip
4	+3	2	max(0, 2+3)=5	5	new max
5	-2	5	max(0, 5-2)=3	5	still positive

✅ max_profit = 5, same as correct answer (buy at 1, sell at 6).