How do you solve Best Time to Buy and Sell Stock?

Use two pointers l and r initialized to 0 and 1. Iterate r through the array. If prices[l] < prices[r], update max_profit with prices[r] - prices[l]. Otherwise, move l to r. Increment r each iteration. Return max_profit after the loop completes.

Best Time to Buy and Sell Stock

Q: What is the time complexity of Best Time to Buy and Sell Stock?

O(n). The algorithm makes a single pass through the prices array with two pointers, each moving forward at most n times.

Q: What pattern does Best Time to Buy and Sell Stock use?

The Pattern: Greedy Algorithms (Two Pointers for Optimal Substructure) The Heuristic: Track the lowest buying price seen so far and greedily update the maximum profit by comparing it with each future price; when a new lower price is found, reset the buying point to maintain the best potential profit.

Easy Greedy Algorithms

Problem

Given an array prices where prices[i] is the price of a given stock on the ith day, return the maximum profit you can achieve by choosing a single day to buy one stock and a different day in the future to sell that stock.

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴

Example

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

Output: 5

The algorithm starts with two pointers: l at index 0 (price 7) and r at index 1 (price 1). Since prices[l] (7) is not less than prices[r] (1), l moves to r (index 1). Then r advances to index 2 (price 5). Now prices[l] (1) < prices[r] (5), so profit is 4 and max_profit updates to 4. The process continues, updating max_profit to 5 when r reaches index 4 (price 6). The final max_profit is 5, achieved by buying at price 1 and selling at price 6.

Approach

Straightforward Solution

A brute-force approach checks every pair of days (buy and sell), resulting in O(n^2) time, which is too slow for large inputs.

Core Observation

The maximum profit is the largest difference between a later selling price and an earlier buying price. This requires tracking the minimum price seen so far and comparing it to future prices.

Path to Optimal

Preview

The key insight is to use two pointers: one tracking the minimum price (buy day) and the other scanning forward (sell day). If the current sell price is higher than the buy price, calculate profit and update max profit…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers l and r initialized to 0 and 1. Iterate r through the array…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes a single pass through the prices array with two pointers, each moving forward at most n times.

Space

O(1)

Only a fixed number of variables are used to track pointers and maximum profit, independent of input size.

Pattern Spotlight

Greedy Algorithms (Two Pointers for Optimal Substructure)

Track the lowest buying price seen so far and greedily update the maximum profit by comparing it with each future price; when a new lower price is found, reset the buying point to maintain the best potential profit.

Solution

Python

1class Solution:
  def maxProfit(self, prices: list[int]) -> int:
      l, r = 0, 1
      max_profit = 0
5
      while r < len(prices):
          if prices[l] < prices[r]:
              profit = prices[r] - prices[l]
              max_profit = max(max_profit, profit)
          else:
              l = r
          r += 1
          
      return max_profit

Step-by-Step Solution

Initialize Two Pointers and Maximum Profit Tracker

3l, r = 0, 1
4max_profit = 0

Objective

To set up pointers for the buy day (l) and sell day (r), and initialize the maximum profit to zero.

Key Insight

Starting with l at 0 and r at 1 ensures the algorithm compares prices in chronological order, respecting the constraint that selling must occur after buying. Initializing max_profit to zero handles cases where no profit is possible.

Interview Quick-Check

Core Logic

Pointers l and r represent the buy and sell days respectively, maintaining the chronological order required for valid transactions.

State & Boundaries

Initialize max_profit to zero to correctly handle cases where prices never increase.

Iterate Through Prices to Update Profit and Buy Pointer

To scan through the prices array, updating max_profit when a profitable sell is found, or moving the buy pointer when a lower price is encountered.

Return the Maximum Profit Found

To output the maximum profit calculated after scanning all prices.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

max_profit = max(max_profit, profit)

Update max_profit if the current profit is greater than the previous maximum.

This line is the critical step that maintains the global maximum profit by comparing the current profit to the best known, ensuring the algorithm returns the optimal solution.

Line 11 Critical

l = r

Move the buy pointer to the current sell pointer.

This line is crucial because it updates the buying day to the lowest price seen so far, enabling the greedy strategy to find the maximum profit by always buying at the lowest price before selling.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does moving the buy pointer to the sell pointer when prices[r] <= prices[l] guarantee correctness?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Best Time to Buy and Sell Stock from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Best Time to Buy and Sell Stock drill

or drill a free problem

1	`class Solution:`
2	`def maxProfit(self, prices: list[int]) -> int:`
3	`l, r = 0, 1`
4	`max_profit = 0`
5
6	`while r < len(prices):`
7	`if prices[l] < prices[r]:`
8	`profit = prices[r] - prices[l]`
9	`max_profit = max(max_profit, profit)`
10	`else:`
11	`l = r`
12	`r += 1`
13
14	`return max_profit`