Log inSign up
easyLeetCodeNot Started

Best Time to Buy and Sell Stock

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1 · Standard Profitable Trade:

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2 · Monotonically Decreasing Prices (No Profit):

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: In this case, no transaction is done and the max profit = 0 because prices strictly decline.

Example 3 · Single Day / Minimum Length:

Input: prices = [5]
Output: 0
Explanation: Cannot sell on a different future day, so maximum profit is 0.

Example 4 · Lowest Price on Last Day:

Input: prices = [2, 4, 1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4) -> profit = 2. Even though price drops to 1 on day 3, you cannot sell after day 3.

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104
  • You must buy before you can sell (selling day > buying day).

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array traversal and element access
  • Running minimum variable updates
  • Basic understanding of time-ordered constraints (buy must precede sell)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify problems requiring a single forward scan with running state tracking.
  • Formulate the invariant: max profit selling on day i is prices[i] - min(prices[0...i-1]).
  • Eliminate auxiliary memory from O(N) to O(1) by updating the running minimum on the fly.
  • Implement clean, standalone solutions in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem requires finding maximum difference between two elements (nums[j] - nums[i]) where j > i.
  • Temporal constraint: earlier element must be matched with later element.
  • Input is an array of continuous time-series numbers.

Algorithmic Decision Tree:

  • When finding max (current - previous_best) in time order -> Maintain a running minimum variable (O(N) time, O(1) space).
  • If multiple transactions allowed -> Greedy local peak-valley traversal (Best Time to Buy & Sell Stock II).
  • If at most K transactions with cooldown -> State Machine Dynamic Programming.

Connected Patterns:

Running Minimum / Prefix MinKadane's AlgorithmPeak Valley GreedyState Machine DP

1. Brute Force — Check All (Buy, Sell) Pairs

Intuition

Evaluate every possible buy day i and sell day j (where j > i), calculate profit = prices[j] - prices[i], and keep the maximum.

Algorithm

  1. Initialize maxProfit = 0.
  2. Loop i from 0 to N - 2 (buy day).
  3. Nested loop j from i + 1 to N - 1 (sell day).
  4. Calculate profit = prices[j] - prices[i].
  5. Update maxProfit = max(maxProfit, profit).
  6. Return maxProfit.

Approach 1: Brute Force — Check All (Buy, Sell) Pairs Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [7, 1, 5, 3, 6, 4]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Left pointer L anchors at 0
Visual state
Values and pointers at this exact step
pointers
S
7
1
5
3
6
4
0
↑ L (Anchor)↑ R (Scan)
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Current Value
7
Valid Prefix Count
0
Check / comparison
arr[0]=7. Evaluate condition on first element.
Decision / next transition
Setup invariant: left pointer guards valid prefix.
Why this step matters

Phase 1 — Setup: Left pointer L anchors at 0. Scanner pointer R starts traversing the array.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Brute Force: Try all buy and sell pairs
7int maxProfit(const vector<int>& prices) {
8 int n = prices.size();
9 int maxProfitVal = 0;
10
11 for (int i = 0; i < n; i++) {
12 for (int j = i + 1; j < n; j++) {
13 int profit = prices[j] - prices[i];
14 maxProfitVal = max(maxProfitVal, profit);
15 }
16 }
17 return maxProfitVal;
18}
19
20int main() {
21 vector<int> prices = {7, 1, 5, 3, 6, 4};
22 cout << "Max Profit: " << maxProfit(prices) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(N²) — Nested loops inspect all N × (N - 1) / 2 pairs, leading to O(N²) quadratic time complexity.
  • Space complexity: O(1) — Only scalar variables (maxProfitVal, i, j) are stored in constant memory.

Why Brute Force Doesn't Scale:

For N = 100,000 days, N² / 2 ≈ 5,000,000,000 operations (5 billion checks), exceeding the standard 1-second limit.

Key Insight: We do not need to check all historical buying days. If we sell on day i, the ONLY buying day that matters is the day with the lowest price up to day i. Maintaining a single minPrice variable reduces the complexity to a single pass.

For N = 105: Brute force takes ~5B ops (TLE). Single pass takes ~100K ops (~1ms).

2. Better — Two Pointers (Sliding Window)

Intuition

Use a sliding window where the left pointer l represents the buying day and the right pointer r represents the selling day. If prices[l] < prices[r], this transaction is profitable: we calculate currentProfit = prices[r] - prices[l] and update maxProfit. If prices[r] <= prices[l], we discovered a new minimum price to buy at; therefore, we shift l = r. We advance r at every iteration to check the next selling day.

Algorithm

  1. Initialize l = 0 (buy day) and r = 1 (sell day), with maxProfit = 0.
  2. Loop while r < prices.length.
  3. Check if prices[l] < prices[r] (profitable trade).
  4. If profitable: compute profit = prices[r] - prices[l] and update maxProfit = max(maxProfit, profit).
  5. Else (prices[r] <= prices[l]): we found a cheaper buying day, so shift l = r.
  6. Advance r += 1 to examine the next day.
  7. Return maxProfit after r scans all days.

Two Pointers (Sliding Window) Granular Trace

2 of 2 questions left today
Step 1 / 11
Trace timeline9% explored
InputINPUT nums = [7, 1, 5, 3, 6, 4]
Current operationSTEP 1 OF 11
Phase 1 — Initialization & Baseline Setup: We initialize our buy pointer l = 0 on Day 0 (price $7) and sell pointer r = 1 on Day 1 (price $1), with maxProfit = 0
Visual state
Values and pointers at this exact step
array
S
7
1
5
3
6
4
0
↑ L (Buy)
1
↑ R (Sell)
2
3
4
5
Variables at this step
Current Phase
1
Inspected Value
7
Condition Met
false
Running Status
Evaluating
Check / comparison
prices[l] = 7, prices[r] = 1. Condition: 7 < 1 is FALSE (Loss of -6)
Decision / next transition
Do not execute trade. Price drop detected.
Why this step matters

Phase 1 — Initialization & Baseline Setup: We initialize our buy pointer l = 0 on Day 0 (price 7) and sell pointer r = 1 on Day 1 (price 1), with maxProfit = 0. Evaluating prices[l] < prices[r] (7 < 1) evaluates to FALSE. Buying at 7 and selling at 1 results in a loss of -$6, which cannot yield a valid trade.

Step 1 / 11
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6class Solution {
7public:
8 // Two Pointers (Sliding Window)
9 int maxProfit(const vector<int>& prices) {
10 int l = 0; // Buy pointer
11 int r = 1; // Sell pointer
12 int maxProfitVal = 0;
13
14 while (r < (int)prices.size()) {
15 if (prices[l] < prices[r]) {
16 int profit = prices[r] - prices[l];
17 maxProfitVal = max(maxProfitVal, profit);
18 } else {
19 l = r; // Found a cheaper buy day
20 }
21 r++; // Move sell pointer forward
22 }
23 return maxProfitVal;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> prices = {7, 1, 5, 3, 6, 4};
30 cout << "Max Profit: " << sol.maxProfit(prices) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Both left (buy) and right (sell) pointers traverse the array of length N at most once, performing constant O(1) checks per step. Total time is O(N).
  • Space complexity: O(1) — Only two pointer indices (l, r) and the maxProfit variable are tracked in memory. O(1) auxiliary space.

3. Optimal — Single Pass Running Minimum

Intuition

Maintain the minimum price seen so far in a single forward pass. At each day, calculate profit if selling today and update the global max profit.

Algorithm

  1. Initialize minPrice = prices[0] (or infinity) and maxProfit = 0.
  2. Iterate through each price in prices.
  3. Calculate currentProfit = price - minPrice.
  4. Update maxProfit = max(maxProfit, currentProfit).
  5. Update minPrice = min(minPrice, price).
  6. Return maxProfit after the loop.

Approach 3: Optimal — Single Pass Running Minimum Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [7, 1, 5, 3, 6, 4]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Left pointer L anchors at 0
Visual state
Values and pointers at this exact step
pointers
S
7
1
5
3
6
4
0
↑ L (Anchor)↑ R (Scan)
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Current Value
7
Valid Prefix Count
0
Check / comparison
arr[0]=7. Evaluate condition on first element.
Decision / next transition
Setup invariant: left pointer guards valid prefix.
Why this step matters

Phase 1 — Setup: Left pointer L anchors at 0. Scanner pointer R starts traversing the array.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <climits>
3#include <iostream>
4#include <vector>
5using namespace std;
6
7// Optimal: Single Pass Running Minimum
8int maxProfit(const vector<int>& prices) {
9 int minPrice = INT_MAX;
10 int maxProfitVal = 0;
11
12 for (int price : prices) {
13 // Track the lowest buying price seen so far
14 minPrice = min(minPrice, price);
15 // Calculate profit if sold today
16 maxProfitVal = max(maxProfitVal, price - minPrice);
17 }
18 return maxProfitVal;
19}
20
21int main() {
22 vector<int> prices = {7, 1, 5, 3, 6, 4};
23 cout << "Max Profit: " << maxProfit(prices) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N) — The array is traversed exactly once from start to finish in a single loop of N iterations, performing constant O(1) comparisons per element. Total time = O(N).
  • Space complexity: O(1) — Only two integer variables (minPrice and maxProfitVal) are maintained throughout the scan. Zero extra memory is allocated.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All Buy/Sell PairsO(N²)O(1)Test every valid (buy_day, sell_day) pair with nested loops.Re-scanning all future days for every buying day.
2.Better — Two Pointers (Sliding Window)O(N)O(1)Maintain left (buy) and right (sell) pointers. If prices[l] < prices[r], record profit; else shift l = r because a cheaper buying day was found.Pointer sliding logic vs simple running min variable.
3.Optimal — Single Pass Running MinimumOptimalO(N)O(1)Maintain minPrice so far. At each price, update maxProfit = max(maxProfit, price - minPrice).Optimal in both time and space.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Finding the global minimum and global maximum of the entire array without respecting time order (e.g. buying after selling).

Pitfall 2:

Initializing maxProfit to negative infinity instead of 0 (problem requires returning 0 if no profit is possible).

Pitfall 3:

Using a nested loop (O(N²)) which results in Time Limit Exceeded for N = 105.

Crucial Edge Cases to Validate:

  • Strictly decreasing array ([7, 6, 4, 3, 1]) -> max profit is 0 (no profitable transaction possible).
  • Strictly increasing array ([1, 2, 3, 4, 5]) -> buy on day 1 (1) and sell on last day (5), profit = 4.
  • Single element array ([5]) -> cannot sell on a future day, returns 0.
  • Lowest price is on the very last day ([3, 5, 1]) -> buy at 3, sell at 5 -> profit 2. Cannot sell after the last day.
  • All prices identical ([4, 4, 4, 4]) -> profit is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the temporal constraint out loud: 'We cannot simply take max(prices) - min(prices) because buy must occur before sell.'
  2. Explain the transition from O(N²) brute force to O(N) single pass by shifting perspective from 'when should I sell after buying' to 'what was the best price to have bought if I sell today'.
  3. Highlight that the space complexity is strictly O(1) constant auxiliary space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Best Time to Buy and Sell Stock?

2.Why is the brute force approach suboptimal for large inputs in Best Time to Buy and Sell Stock?

3.Which data structure or technique enables the optimal solution for Best Time to Buy and Sell Stock?

Back to DSA Sheet