Jobs

Interviews

Discussions

Best Time to Buy and Sell Stock #28 Most Asked

Easy

ByteDance

1 view

Topics:

ArraysDynamic Programming

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 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 <= 10⁵
0 <= prices[i] <= 10⁴

Try coding it in LeetCode

Best Time to Buy and Sell Stock #28 Most Asked

Easy

ByteDance

1 view

Topics:

ArraysDynamic Programming

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 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 <= 10⁵
0 <= prices[i] <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the stock prices in the input array? For instance, can prices be zero or negative?
What should be the output if the input array is empty or contains only a single element?
Does the order of the prices array represent chronological days, meaning I must buy before I can sell?
Can the input array contain duplicate price values, and if so, does that change the logic in any way?
Is the input guaranteed to be an array of integers, or could it contain other data types or be null?

Brute Force Solution

Approach

To find the biggest possible profit, we'll try out every single valid option. This means we will check every possible day to buy the stock and, for each of those days, we'll check every possible future day to sell it.

Here's how the algorithm would work step-by-step:

First, imagine you buy the stock on the very first day.
Now, calculate the potential profit if you were to sell it on the second day, then the third day, and so on, until the very last day.
Keep a note of the best profit you've found so far from all these possibilities.
Next, forget about buying on the first day and imagine you buy on the second day instead.
Again, calculate the profit you'd make by selling on each of the following days (the third, fourth, etc.).
If any of these new profits are better than the best one you've noted down, update your note with the new highest profit.
Repeat this entire process for every single day, always pretending to buy on that day and then checking all the later days for selling.
After you have considered every single combination of buying and then selling on a future day, the highest profit you've noted down will be your answer.

Code Implementation

def maxProfit(prices):
    maximum_profit_found = 0

    # Iterate through each day as a potential day to buy the stock.
    for buy_day_index in range(len(prices)):

        # For each buy day, check all subsequent days as potential sell days.
        for sell_day_index in range(buy_day_index + 1, len(prices)):
            buy_price = prices[buy_day_index]
            sell_price = prices[sell_day_index]

            potential_profit = sell_price - buy_price

            # If this combination yields a better profit, we must update our record of the best one.
            if potential_profit > maximum_profit_found:
                maximum_profit_found = potential_profit

    return maximum_profit_found

Big(O) Analysis

Time Complexity

O(n²) – The time complexity is driven by a nested loop structure where we check every possible pair of buy and sell days. The outer loop iterates through each potential buy day, from the first to the last, which runs n times where n is the number of days. For each of these buy days, the inner loop iterates through all subsequent sell days to calculate the profit. This leads to a total number of operations roughly proportional to (n-1) + (n-2) + ... + 1, which approximates to n * (n-1) / 2. Therefore, the overall time complexity simplifies to O(n²).

Space Complexity

O(1) – The algorithm described iterates through all possible buy and sell combinations but only needs to store a single variable to keep track of the maximum profit found so far. This variable is updated whenever a larger profit is calculated. Since the amount of extra memory used does not depend on the number of days (N) in the input price list, the auxiliary space complexity is constant.

Optimal Solution

Approach

The goal is to find the largest possible profit from a single buy and sell transaction. The most efficient way to do this is to go through the historical prices just once, keeping track of the lowest price seen so far and continuously calculating the potential profit if we were to sell on the current day.

Here's how the algorithm would work step-by-step:

Imagine you're walking through the list of daily prices, one day at a time.
Keep a mental note of the absolute cheapest price you've encountered on any day up to this point.
On each new day, consider the current price. Ask yourself: 'If I sold my stock today, what would my profit be?' Your profit would be the current day's price minus the cheapest price you've seen so far.
Compare this potential profit with the best profit you've found on any previous day. If this new profit is bigger, it becomes your new best-profit-so-far.
After checking the profit, also check if the current day's price is a new all-time low. If it is, update your mental note of the cheapest price.
Continue this process for every single day in the list.
By the time you reach the end, the best profit you've recorded will be the maximum possible profit you could have made.

Code Implementation

def maxProfit(prices):
    # Initialize with the first day's price as we need a starting point to compare against.
    cheapest_price_so_far = float('inf')

    best_profit_so_far = 0

    for current_price in prices:
        # Calculate profit if we sell today, using the cheapest buy price found before today.
        potential_profit = current_price - cheapest_price_so_far

        # If today's potential profit is the best we've seen, we update our maximum profit.
        if potential_profit > best_profit_so_far:
            best_profit_so_far = potential_profit

        # Check if the current day's price is a new low, to find better future buy opportunities.
        if current_price < cheapest_price_so_far:
            cheapest_price_so_far = current_price

    return best_profit_so_far

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the single pass through the list of stock prices. If the input list has n prices, the algorithm will iterate through each of the n items exactly once. Inside this single loop, we perform a constant number of operations: a comparison to find the potential profit and another comparison to update the minimum price seen so far. Since the number of operations is directly proportional to the size of the input list, n, the time complexity simplifies to O(n).

Space Complexity

O(1) – The algorithm's space usage is constant because it only requires a few variables to operate: one to store the minimum price found so far and another to store the maximum profit calculated. These variables occupy a fixed amount of memory, regardless of the number of prices in the input list, which we can denote as N. Therefore, the auxiliary space complexity does not grow with the size of the input.

Edge Cases

Case	How to Handle
Empty or null input array	The problem constraints typically guarantee a non-empty array, but a robust solution should handle this by returning 0 as no transactions are possible.
Input array with only one element	No transaction is possible as you cannot buy and sell on the same day, so the maximum profit must be 0.
Prices are strictly decreasing (e.g., [10, 8, 5, 2])	The algorithm will correctly find no profitable transaction and return 0, as the max profit will never become positive.
All prices in the array are identical (e.g., [7, 7, 7, 7])	The maximum profit will remain 0 throughout the process since the difference between any sell price and the minimum buy price is always zero.
The minimum price occurs on the last day	No sale can be made after the last day, so the algorithm correctly produces a profit of 0 if all previous prices were higher.
The maximum price occurs on the first day	The algorithm will set the first price as the initial minimum but will correctly find no profitable selling opportunity if all subsequent prices are lower.
Large input array size (e.g., 10^5 elements)	A single-pass O(N) solution is efficient and scales linearly, avoiding timeouts that would occur with a brute-force O(N^2) approach.
Input contains zero as a price	A price of zero is a valid non-negative integer and is handled correctly by the algorithm when tracking the minimum price and calculating profit.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the stock prices in the input array? For instance, can prices be zero or negative?
What should be the output if the input array is empty or contains only a single element?
Does the order of the prices array represent chronological days, meaning I must buy before I can sell?
Can the input array contain duplicate price values, and if so, does that change the logic in any way?
Is the input guaranteed to be an array of integers, or could it contain other data types or be null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine you buy the stock on the very first day.
Now, calculate the potential profit if you were to sell it on the second day, then the third day, and so on, until the very last day.
Keep a note of the best profit you've found so far from all these possibilities.
Next, forget about buying on the first day and imagine you buy on the second day instead.
Again, calculate the profit you'd make by selling on each of the following days (the third, fourth, etc.).
If any of these new profits are better than the best one you've noted down, update your note with the new highest profit.
Repeat this entire process for every single day, always pretending to buy on that day and then checking all the later days for selling.
After you have considered every single combination of buying and then selling on a future day, the highest profit you've noted down will be your answer.

Code Implementation

def maxProfit(prices):
    maximum_profit_found = 0

    # Iterate through each day as a potential day to buy the stock.
    for buy_day_index in range(len(prices)):

        # For each buy day, check all subsequent days as potential sell days.
        for sell_day_index in range(buy_day_index + 1, len(prices)):
            buy_price = prices[buy_day_index]
            sell_price = prices[sell_day_index]

            potential_profit = sell_price - buy_price

            # If this combination yields a better profit, we must update our record of the best one.
            if potential_profit > maximum_profit_found:
                maximum_profit_found = potential_profit

    return maximum_profit_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're walking through the list of daily prices, one day at a time.
Keep a mental note of the absolute cheapest price you've encountered on any day up to this point.
On each new day, consider the current price. Ask yourself: 'If I sold my stock today, what would my profit be?' Your profit would be the current day's price minus the cheapest price you've seen so far.
Compare this potential profit with the best profit you've found on any previous day. If this new profit is bigger, it becomes your new best-profit-so-far.
After checking the profit, also check if the current day's price is a new all-time low. If it is, update your mental note of the cheapest price.
Continue this process for every single day in the list.
By the time you reach the end, the best profit you've recorded will be the maximum possible profit you could have made.

Code Implementation

def maxProfit(prices):
    # Initialize with the first day's price as we need a starting point to compare against.
    cheapest_price_so_far = float('inf')

    best_profit_so_far = 0

    for current_price in prices:
        # Calculate profit if we sell today, using the cheapest buy price found before today.
        potential_profit = current_price - cheapest_price_so_far

        # If today's potential profit is the best we've seen, we update our maximum profit.
        if potential_profit > best_profit_so_far:
            best_profit_so_far = potential_profit

        # Check if the current day's price is a new low, to find better future buy opportunities.
        if current_price < cheapest_price_so_far:
            cheapest_price_so_far = current_price

    return best_profit_so_far

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	The problem constraints typically guarantee a non-empty array, but a robust solution should handle this by returning 0 as no transactions are possible.
Input array with only one element	No transaction is possible as you cannot buy and sell on the same day, so the maximum profit must be 0.
Prices are strictly decreasing (e.g., [10, 8, 5, 2])	The algorithm will correctly find no profitable transaction and return 0, as the max profit will never become positive.
All prices in the array are identical (e.g., [7, 7, 7, 7])	The maximum profit will remain 0 throughout the process since the difference between any sell price and the minimum buy price is always zero.
The minimum price occurs on the last day	No sale can be made after the last day, so the algorithm correctly produces a profit of 0 if all previous prices were higher.
The maximum price occurs on the first day	The algorithm will set the first price as the initial minimum but will correctly find no profitable selling opportunity if all subsequent prices are lower.
Large input array size (e.g., 10^5 elements)	A single-pass O(N) solution is efficient and scales linearly, avoiding timeouts that would occur with a brute-force O(N^2) approach.
Input contains zero as a price	A price of zero is a valid non-negative integer and is handled correctly by the algorithm when tracking the minimum price and calculating profit.

0/0 ByteDance questions completed

0/0 completed