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

The optimal solution has a time complexity of O(n).

What data structures are used to solve Best Time to Buy and Sell Stock?

This problem uses Array, Dynamic Programming. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Best Time to Buy and Sell Stock?

The core insight is to continuously track the lowest price encountered *up to the current day*. For any given `price` we're currently looking at as a potential sell point, the best possible profit comes from buying at the lowest point *before or on* that day. This problem doesn't require us to store all possible buy/sell pairs or look ahead into the future. By maintaining `min_price` as a running minimum, we ensure that every potential profit calculation (`current_price - min_price`) correctly considers the 'buy before sell' constraint with the most optimal buy point seen so far.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Best Time to Buy and Sell Stock - LeetCode 121 Solution

Q: Which companies ask LeetCode 121. Best Time to Buy and Sell Stock in interviews?

This problem is frequently asked at AQR Capital Management, Accenture, Accolite, Agoda, Airtel and 107 more companies.

Best Time to Buy and Sell Stock - Complete Solution Guide

Best Time to Buy and Sell Stock is LeetCode problem 121, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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: 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

Detailed Explanation

This problem asks us to pinpoint the optimal single day to buy a stock and a subsequent single day to sell it, all with the goal of maximizing our profit. The input is a simple array where each element `prices[i]` represents the stock's value on day `i`. The crucial constraint here is that you *must* sell on a day *after* you buy. You can't buy and sell on the same day, nor can you sell before you've bought the stock. What makes this interesting isn't just finding the absolute lowest price and the absolute highest price in the `prices` array. For instance, in `[7,1,5,3,6,4]`, the lowest price is 1 and the highest is 7. But you can't buy at 1 (day 2) and sell at 7 (day 1) because the buy date must precede the sell date. Instead, we need to find the largest difference `prices[sell_day] - prices[buy_day]` such that `sell_day > buy_day`. If no such profitable transaction is possible (e.g., prices only ever go down), we should return 0. The challenge lies in efficiently iterating through the prices while respecting the 'buy before sell' rule. A naive approach might involve checking every possible buy day and then every possible sell day after it, leading to a much slower solution. We need a way to keep track of the best buying opportunity up to any given point as we consider potential selling days.

Solution Approach

The provided solution employs a clever single-pass strategy to tackle this problem. It iterates through the `prices` array just once, maintaining two critical pieces of information: `min_price` and `max_profit`. `min_price` tracks the lowest stock price encountered *so far* as we traverse the array. When we are at `prices[i]`, `min_price` holds the absolute minimum value from `prices[0]` to `prices[i-1]` (or `prices[i]` itself if `prices[i]` is a new minimum). This is crucial because for any `prices[i]` we consider as a potential selling point, the optimal buy point *before or on day i* is precisely this `min_price`. We update `min_price = min(min_price, price)` to ensure it always reflects the best buying opportunity seen up to the current day. Simultaneously, `max_profit` tracks the highest profit calculated across all days. For each `price` (current day's stock price), we calculate a potential profit: `price - min_price`. This difference represents the profit if we were to sell on the current day (`price`) after having bought on the day corresponding to `min_price`. Since `min_price` is always updated to be the lowest price encountered *up to or including the current day*, this profit calculation inherently respects the 'buy before sell' constraint. We then update `max_profit = max(max_profit, current_potential_profit)` to retain the highest profit found so far. By the time the loop finishes, `max_profit` will hold the maximum achievable profit from any single transaction.

Step-by-Step Algorithm

Step 1: Initialize `min_price` to a very large value (positive infinity in Python, Integer.MAX_VALUE in Java, INT_MAX in C++) and `max_profit` to 0.
Step 2: Iterate through the `prices` array.
Step 3: For each `price`, update `min_price` to the minimum of `min_price` and `price`.
Step 4: Calculate the current profit as `price - min_price`.
Step 5: Update `max_profit` to the maximum of `max_profit` and the current profit.
Step 6: After iterating through all prices, return `max_profit`.

Key Insights

The core insight is to continuously track the lowest price encountered *up to the current day*. For any given `price` we're currently looking at as a potential sell point, the best possible profit comes from buying at the lowest point *before or on* that day.
This problem doesn't require us to store all possible buy/sell pairs or look ahead into the future. By maintaining `min_price` as a running minimum, we ensure that every potential profit calculation (`current_price - min_price`) correctly considers the 'buy before sell' constraint with the most optimal buy point seen so far.
The solution's elegance comes from its O(N) time complexity and O(1) space complexity. A single pass through the array, updating just two variables, is sufficient because the global maximum profit can always be found by comparing the current price with the best preceding buy price.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming.

Companies

Asked at: AQR Capital Management, Accenture, Accolite, Agoda, Airtel, Akamai, American Express, Arista Networks, Atlassian, BNY Mellon, Bank of America, Bentley Systems, BlackRock, Blizzard, Bolt, ByteDance, CME Group, Capgemini, Capital One, Cisco, Citadel, Citigroup, Cloudera, CrowdStrike, DE Shaw, DRW, Deloitte, Deutsche Bank, DevRev, EPAM Systems, Expedia, FPT, Flipkart, FreshWorks, Garmin, Goldman Sachs, Groww, HSBC, HashedIn, IBM, Infosys, Instacart, Intel, Intuit, J.P. Morgan, LinkedIn, Mastercard, Media.net, Microstrategy, Millennium, Morgan Stanley, Myntra, Netflix, Nutanix, Nvidia, Ola Cabs, Optiver, Oracle, Ozon, Palantir Technologies, PayPal, PhonePe, Pwc, QBurst, RBC, Rakuten, Remitly, Robinhood, Roblox, SAP, Salesforce, Samsung, ServiceNow, Shopee, Siemens, Slice, Snap, Snapdeal, Snowflake, Societe Generale, Sony, Sprinklr, Swiggy, Tech Mahindra, Tekion, Tesla, The Trade Desk, ThoughtWorks, Tiger Analytics, TikTok, Toast, Tripadvisor, Turing, Two Sigma, UBS, UKG, Uber, VMware, Visa, Walmart Labs, Yahoo, Yandex, Zoho, Zoox, Zopsmart, athenahealth, carwale, eBay, josh technology, opentext, tcs, zeta suite.

Best Time to Buy and Sell Stock | LeetCode 121

Easy

Array Dynamic Programming

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 121: Best Time to Buy and Sell Stock - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming

Companies

AQR Capital ManagementAccentureAccoliteAgodaAirtelAkamaiAmerican ExpressArista Networks

Stats

Difficulty:Easy

Languages:4

Companies:112

Problem #:121

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize `min_price` to a very large value (positive infinity in Python, Integer.MAX_VALUE in Java, INT_MAX in C++) and `max_profit` to 0.
2
Step 2: Iterate through the `prices` array.
3
Step 3: For each `price`, update `min_price` to the minimum of `min_price` and `price`.
4
Step 4: Calculate the current profit as `price - min_price`.
5
Step 5: Update `max_profit` to the maximum of `max_profit` and the current profit.
6
Step 6: After iterating through all prices, return `max_profit`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The solution iterates through the `prices` array once, so the time complexity is linear. It uses a constant amount of extra space to store `min_price` and `max_profit`, resulting in constant space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

This approach iterates through all possible pairs of buy and sell days and finds the maximum profit. It uses nested loops.

Time: O(n^2)Space: O(1)

Trade-offs: This approach is less efficient than the optimal solution (O(n^2) vs O(n)). It's only suitable for very small input sizes.

✨

Key Insights

1The core insight is to continuously track the lowest price encountered *up to the current day*. For any given `price` we're currently looking at as a potential sell point, the best possible profit comes from buying at the lowest point *before or on* that day.
2This problem doesn't require us to store all possible buy/sell pairs or look ahead into the future. By maintaining `min_price` as a running minimum, we ensure that every potential profit calculation (`current_price - min_price`) correctly considers the 'buy before sell' constraint with the most optimal buy point seen so far.
3The solution's elegance comes from its O(N) time complexity and O(1) space complexity. A single pass through the array, updating just two variables, is sufficient because the global maximum profit can always be found by comparing the current price with the best preceding buy price.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Empty `prices` array. The solution correctly handles this by returning 0 as no profit is possible.
Edge case 2: Prices are monotonically decreasing (e.g., [7, 6, 4, 3, 1]). The solution correctly handles this by returning 0, as no profit is possible.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to initialize `min_price` to a sufficiently large value. This can lead to incorrect results if the first few prices are greater than subsequent prices.

✗Common mistake 2: Not considering the edge case of monotonically decreasing prices where no profit is possible. The solution must return 0 in this scenario.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Algorithmic trading. This algorithm can be part of a larger system to determine optimal buy and sell points for stocks based on historical data.

🏦Real-world scenario 2: Inventory management. Determining the best time to buy raw materials and sell finished goods, maximizing profit margins.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 30, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Best Time to Buy and Sell Stock"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?