Skip to main content
Talentd

Best Time to Buy and Sell Stock - Solution & Explanation

EasyArrayDynamic Programming18 min readAsked at: Bank of America, Amazon, Microsoft +89
Practice this problem

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith 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:

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:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Approach Overview

Problem Overview: You are given an array where prices[i] is the stock price on day i. You must choose one day to buy and a later day to sell to maximize profit. If no profitable transaction exists, return 0.

Approach 1: Brute Force (O(n²) time, O(1) space)

The straightforward solution checks every possible pair of days. For each day i, treat it as the buying day and compare it with every later day j as the selling day. Compute the profit prices[j] - prices[i] and track the maximum value. This approach uses nested loops over the array, so the time complexity grows quadratically. It works for small inputs and helps verify the logic of the problem, but becomes slow for large datasets.

Approach 2: Single Pass with Tracking Minimum Price (O(n) time, O(1) space)

The optimal solution scans the array once while maintaining the lowest price seen so far. At each step, treat the current price as a potential selling price and compute the profit using currentPrice - minPrice. If this profit exceeds the best profit recorded so far, update the result. Otherwise, update minPrice when a lower price appears. This works because the best transaction must buy at the lowest price before the sell day.

This technique resembles a simplified dynamic programming or greedy strategy: maintain state (minPrice) while iterating through the array and update the best answer incrementally. Only two variables are required, so space usage stays constant. The algorithm performs exactly one pass over the data, making it efficient even for very large inputs.

Recommended for interviews: Interviewers expect the single-pass minimum tracking approach. The brute force solution demonstrates baseline reasoning and correctness, but the O(n) scan shows you recognize the key insight: the best sell decision depends only on the smallest price seen before that day. Implementing this efficiently with constant space is the standard interview solution.

Approach 1: Approach 1: Single Pass with Tracking Minimum Price

In this approach, we traverse the prices array while keeping track of the minimum price seen so far and calculate the maximum profit we could achieve if we sold on that day. The maximum profit is updated accordingly through each iteration.

This approach makes a single pass through the array (O(n) time complexity) and uses constant space (O(1) space complexity).

This C solution iterates through the given prices array. It maintains the minimum price found so far and calculates potential profit as the difference between the current day's price and the tracked minimum price. The maximum of this profit value is retained.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of days.
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Approach 2: Brute Force (For Educational Purposes)

This approach considers all possible pairs of buy and sell days, calculating the profit for each combination. It is straightforward but inefficient due to its O(n^2) time complexity, which is impractical for large inputs.

This C implementation uses nested loops to check all possible buy and sell day pairs, computing the profit and tracking the highest encountered. It serves as an illustration of the brute force method.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the number of days.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Enumerate + Maintain the Minimum Value of the Prefix

We can enumerate each element of the array nums as the selling price. Then we need to find a minimum value in front of it as the purchase price to maximize the profit.

Therefore, we use a variable mi to maintain the prefix minimum value of the array nums. Then we traverse the array nums and for each element v, calculate the difference between it and the minimum value mi in front of it, and update the answer to the maximum of the difference. Then update mi = min(mi, v). Continue to traverse the array nums until the traversal ends.

Finally, return the answer.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHP

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Single Pass with Tracking Minimum Price

Time Complexity: O(n), where n is the number of days.
Space Complexity: O(1).

Approach 2: Brute Force (For Educational Purposes)

Time Complexity: O(n^2), where n is the number of days.
Space Complexity: O(1).

Enumerate + Maintain the Minimum Value of the Prefix—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force (Check All Buy/Sell Pairs)O(n²)O(1)Educational baseline to understand profit calculation and validate logic
Single Pass with Minimum Price TrackingO(n)O(1)Optimal solution for interviews and production; handles large arrays efficiently

Video Solution

Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python • NeetCode • 1,102,026 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Best Time to Buy and Sell Stock easy or hard?
Best Time to Buy and Sell Stock is categorized as an Easy problem on LeetCode with an acceptance rate around the mid‑50% range. The challenge lies in recognizing that you only need to track the minimum price so far instead of checking all possible buy and sell pairs.
Best Time to Buy and Sell Stock Python/Java solution
In Python or Java, iterate through the prices array while tracking minPrice and maxProfit. Update minPrice when a smaller value appears and compute profit using currentPrice minus minPrice. This implementation runs in O(n) time and O(1) space and is typically under 10 lines of code.
How to solve Best Time to Buy and Sell Stock in O(n)?
Iterate through the price array while tracking the smallest price encountered so far. At each step calculate potential profit as prices[i] minus minPrice and update the maximum profit. If the current price is lower than minPrice, update it. This single pass guarantees O(n) time and constant space.
What is the best approach for Best Time to Buy and Sell Stock?
The best approach is a single-pass scan that tracks the minimum stock price seen so far. For each price, compute the profit if you sold that day using currentPrice minus minPrice. Update the maximum profit and minimum price while iterating. This runs in O(n) time and O(1) space.
Is Best Time to Buy and Sell Stock asked at Google/Amazon/Meta?
Best Time to Buy and Sell Stock is a common interview question across large tech companies including Amazon, Google, Meta, and Microsoft. It tests understanding of array traversal, greedy thinking, and recognizing optimization opportunities from a brute force approach.
What data structure is used in Best Time to Buy and Sell Stock?
The problem primarily uses a simple array traversal. The optimal algorithm maintains two variables—minimum price so far and maximum profit—while iterating through the array, so no additional data structures like hash maps or stacks are required.
What is the time complexity of Best Time to Buy and Sell Stock?
The optimal solution runs in O(n) time because the array is scanned once while maintaining the minimum price and maximum profit. Space complexity is O(1) since only a few variables are stored regardless of input size.

Ready to solve this problem?

Practice Best Time to Buy and Sell Stock with our built-in code editor and test cases.

Practice on FleetCode
Previous

Best Time to Buy and Sell Stock II

Next

Best Time to Buy and Sell Stock III