@meta
title: Best Time to Buy and Sell Stock
questionNo: 6
totalQuestions: 191
sheetLabel: Striver SDE Sheet
sourceLabel: TakeUForward
@endmeta

@page
tag: A
pageNo: 1 / 1
totalPages: 1
@endpage

@section
region: full
title: Problem Statement
content:
You are given an array prices where prices[i] is the stock price on day i.
Choose one day to buy and a later day to sell to maximize profit.
If no profit is possible, return 0.
@endsection

@section
region: left
title: Examples
content:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy at 1 and sell at 6 for profit 5.
---
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: Prices keep falling, so the best choice is no transaction.
@endsection

@section
region: right
title: Custom Notes
content:
- One transaction only.
- Buy must happen before sell.
- Profit today = today's price - minimum price seen earlier.
- Memory hook: min so far, best profit so far.
- Do not confuse this with the multiple-transactions stock problem.
@endsection

@section
region: full
title: Brute Force Approach : TC: SC:
badge: 1 / 3
content:
Algorithm: Try every buy day with every later sell day.
Pseudo:
- For each i, treat prices[i] as buy.
- For each j > i, compute prices[j] - prices[i].
- Track the maximum profit.
Time: O(n^2)
Space: O(1)
Why mention it: Straightforward baseline and makes the single-transaction constraint obvious.
@endsection

@section
region: full
title: Better Approach : TC: SC:
badge: 2 / 3
content:
Algorithm: Precompute the best future sell price for each index and compare.
Pseudo:
- Build a suffixMax array where suffixMax[i] is the maximum price from i to end.
- For each day i, profit = suffixMax[i] - prices[i].
- Track the maximum over all i.
Time: O(n)
Space: O(n)
Interview line: Good transition solution, but we can do the same in constant space.
@endsection

@section
region: full
title: Optimal Approach : TC: SC:
badge: 3 / 3
content:
Algorithm: Maintain minPrice and update maxProfit while scanning once.
Pseudo:
- Initialize minPrice = prices[0] and maxProfit = 0.
- For each price, compute currentProfit = price - minPrice.
- Update maxProfit with currentProfit.
- Update minPrice = min(minPrice, price).
Time: O(n)
Space: O(1)
Key insight: The best buy for today is simply the minimum price that appeared before today.
@endsection

@section
region: grid
title: PCode
badge: 1 / 3
codeLang: pseudo
content:
bestProfit = 0

FOR buy from 0 to n - 1
    FOR sell from buy + 1 to n - 1
        profit = prices[sell] - prices[buy]
        bestProfit = max(bestProfit, profit)

RETURN bestProfit
@endsection

@section
region: grid
title: PCode
badge: 2 / 3
codeLang: pseudo
content:
suffixMax[n - 1] = prices[n - 1]

FOR i from n - 2 down to 0
    suffixMax[i] = max(prices[i], suffixMax[i + 1])

bestProfit = 0

FOR i from 0 to n - 1
    bestProfit = max(bestProfit, suffixMax[i] - prices[i])

RETURN bestProfit
@endsection

@section
region: grid
title: PCode
badge: 3 / 3
codeLang: pseudo
content:
minPrice = prices[0]
bestProfit = 0

FOR each price from left to right
    currentProfit = price - minPrice
    bestProfit = max(bestProfit, currentProfit)
    minPrice = min(minPrice, price)

RETURN bestProfit
@endsection