Jobs

Interviews

Discussions

Best Time to Buy and Sell Stock

#3 Most AskedEasy

Best Time to Buy and Sell Stock #3 Most Asked

Easy

Toast

20 views

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

#3 Most AskedEasy

Best Time to Buy and Sell Stock #3 Most Asked

Easy

Toast

20 views

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 are the constraints on the size of the `prices` array, and what is the expected range of values for each stock price?
If no profit can be made (i.e., prices only decrease or stay the same), what should be returned?
Can the `prices` array be empty or contain only one element?
Are stock prices always positive integers, or can they be zero or floating-point numbers?
Does the problem guarantee that `prices[i]` represents the price at the *end* of the day, or could it be intraday prices?

Brute Force Solution

Approach

This problem is about finding the biggest profit you can make by buying a stock on one day and selling it on a later day. The brute force approach simply checks every single possible pair of buy and sell days.

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

Pick a day to buy the stock.
Then, for that chosen buy day, consider every single day that comes *after* it as a potential sell day.
For each of these buy-sell pairs, calculate how much profit you would make.
Keep track of the largest profit you've found so far.
After you've checked all possible buy-sell pairs, the biggest profit you recorded is your answer.

Code Implementation

def best_time_to_buy_and_sell_stock_brute_force(stock_prices):
    maximum_profit = 0
    number_of_days = len(stock_prices)

    # Iterate through each possible day to buy the stock
    for buy_day_index in range(number_of_days):
        # For the selected buy day, iterate through all subsequent days as potential sell days
        for sell_day_index in range(buy_day_index + 1, number_of_days):
            # Calculate the profit for this buy-sell pair
            current_profit = stock_prices[sell_day_index] - stock_prices[buy_day_index]

            # Update the maximum profit if the current profit is greater
            if current_profit > maximum_profit:
                maximum_profit = current_profit

    return maximum_profit

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach involves two nested loops. The outer loop iterates through each day as a potential buy day, taking up to n iterations where n is the number of days. The inner loop then iterates through all subsequent days as potential sell days for that specific buy day. In the worst case, for the first buy day, the inner loop runs n-1 times, for the second buy day, it runs n-2 times, and so on. This results in a total number of operations that is roughly proportional to the sum of integers from 1 to n-1, which approximates n²/2. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The described brute force solution for finding the best time to buy and sell stock only requires a few variables to store the maximum profit found so far and loop counters. These variables occupy a constant amount of memory regardless of the number of days (N) in the input price list. Therefore, the auxiliary space complexity is constant, O(1).

Optimal Solution

Approach

To find the greatest possible profit, we track the lowest price seen so far and calculate the potential profit if we sold at the current price. We then keep the largest profit we've encountered.

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

Imagine you are going through a list of stock prices day by day.
Keep a note of the absolute lowest price you've seen up to the current day. Think of this as your 'best buying opportunity' so far.
On each new day, look at its price.
Calculate how much money you would make if you had bought at your 'best buying opportunity' and sold on this current day.
Compare this potential profit with the highest profit you've found on any previous day.
If the current day's potential profit is higher, update your record of the 'greatest possible profit'.
Also, if the current day's price is lower than your current 'best buying opportunity', update your 'best buying opportunity' to this new, lower price.
Continue this process for every day in the list.
After checking all the days, the 'greatest possible profit' you've recorded is your answer.

Code Implementation

def calculate_best_stock_profit(stock_prices):
    minimum_buy_price_seen = float('inf')
    maximum_profit_achieved = 0

    for current_day_price in stock_prices:

        # Update the lowest price if the current day's price is lower. This is our new best buying opportunity.
        if current_day_price < minimum_buy_price_seen:
            minimum_buy_price_seen = current_day_price

        # Calculate potential profit by selling at the current price, having bought at the lowest seen so far.
        potential_profit_today = current_day_price - minimum_buy_price_seen

        # Update the maximum profit if the current day's potential profit is greater.
        if potential_profit_today > maximum_profit_achieved:
            maximum_profit_achieved = potential_profit_today

    return maximum_profit_achieved

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the list of stock prices exactly once. For each of the 'n' days (elements in the input array), we perform a constant number of operations: comparing the current price to the minimum price seen so far, calculating a potential profit, and updating the maximum profit if necessary. Since we only traverse the array one time, the total number of operations is directly proportional to the number of elements, 'n'. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The solution requires only a constant amount of extra memory, regardless of the input size N. This is because we only need to store two variables: one to keep track of the lowest price seen so far ('best buying opportunity') and another to store the greatest profit found so far ('greatest possible profit'). The number of these variables does not change with the number of days (N) in the stock price list.

Edge Cases

Case	How to Handle
Empty or null input array	The solution should gracefully handle this by returning 0 profit, as no transaction is possible.
Array with only one element	Since a buy and sell must be on different days, a single element array means no transaction is possible, resulting in 0 profit.
Array with prices strictly decreasing	The algorithm should correctly identify that no profit can be made and return 0.
Array with prices strictly increasing	The algorithm should identify the first day as the buy day and the last day as the sell day to maximize profit.
Array with all identical prices	No profit can be made, so the algorithm should correctly return 0.
Large input array	The solution's linear time complexity ensures efficient handling of large inputs without performance degradation.
Prices containing zero or negative values	The problem statement implies stock prices are non-negative, but if they were allowed, the algorithm would still function correctly by finding the maximum difference.
Maximum possible profit leading to integer overflow	Using a data type that can accommodate the maximum possible profit, such as a 64-bit integer, prevents overflow issues.

Empty or null input array

How to Handle:

The solution should gracefully handle this by returning 0 profit, as no transaction is possible.

Array with only one element

How to Handle:

Since a buy and sell must be on different days, a single element array means no transaction is possible, resulting in 0 profit.

Array with prices strictly decreasing

How to Handle:

The algorithm should correctly identify that no profit can be made and return 0.

Array with prices strictly increasing

How to Handle:

The algorithm should identify the first day as the buy day and the last day as the sell day to maximize profit.

Array with all identical prices

How to Handle:

No profit can be made, so the algorithm should correctly return 0.

Large input array

How to Handle:

The solution's linear time complexity ensures efficient handling of large inputs without performance degradation.

Prices containing zero or negative values

How to Handle:

The problem statement implies stock prices are non-negative, but if they were allowed, the algorithm would still function correctly by finding the maximum difference.

Maximum possible profit leading to integer overflow

How to Handle:

Using a data type that can accommodate the maximum possible profit, such as a 64-bit integer, prevents overflow issues.

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 are the constraints on the size of the `prices` array, and what is the expected range of values for each stock price?
If no profit can be made (i.e., prices only decrease or stay the same), what should be returned?
Can the `prices` array be empty or contain only one element?
Are stock prices always positive integers, or can they be zero or floating-point numbers?
Does the problem guarantee that `prices[i]` represents the price at the *end* of the day, or could it be intraday prices?

Brute Force Solution

Approach

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

Pick a day to buy the stock.
Then, for that chosen buy day, consider every single day that comes *after* it as a potential sell day.
For each of these buy-sell pairs, calculate how much profit you would make.
Keep track of the largest profit you've found so far.
After you've checked all possible buy-sell pairs, the biggest profit you recorded is your answer.

Code Implementation

def best_time_to_buy_and_sell_stock_brute_force(stock_prices):
    maximum_profit = 0
    number_of_days = len(stock_prices)

    # Iterate through each possible day to buy the stock
    for buy_day_index in range(number_of_days):
        # For the selected buy day, iterate through all subsequent days as potential sell days
        for sell_day_index in range(buy_day_index + 1, number_of_days):
            # Calculate the profit for this buy-sell pair
            current_profit = stock_prices[sell_day_index] - stock_prices[buy_day_index]

            # Update the maximum profit if the current profit is greater
            if current_profit > maximum_profit:
                maximum_profit = current_profit

    return maximum_profit

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To find the greatest possible profit, we track the lowest price seen so far and calculate the potential profit if we sold at the current price. We then keep the largest profit we've encountered.

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

Imagine you are going through a list of stock prices day by day.
Keep a note of the absolute lowest price you've seen up to the current day. Think of this as your 'best buying opportunity' so far.
On each new day, look at its price.
Calculate how much money you would make if you had bought at your 'best buying opportunity' and sold on this current day.
Compare this potential profit with the highest profit you've found on any previous day.
If the current day's potential profit is higher, update your record of the 'greatest possible profit'.
Also, if the current day's price is lower than your current 'best buying opportunity', update your 'best buying opportunity' to this new, lower price.
Continue this process for every day in the list.
After checking all the days, the 'greatest possible profit' you've recorded is your answer.

Code Implementation

def calculate_best_stock_profit(stock_prices):
    minimum_buy_price_seen = float('inf')
    maximum_profit_achieved = 0

    for current_day_price in stock_prices:

        # Update the lowest price if the current day's price is lower. This is our new best buying opportunity.
        if current_day_price < minimum_buy_price_seen:
            minimum_buy_price_seen = current_day_price

        # Calculate potential profit by selling at the current price, having bought at the lowest seen so far.
        potential_profit_today = current_day_price - minimum_buy_price_seen

        # Update the maximum profit if the current day's potential profit is greater.
        if potential_profit_today > maximum_profit_achieved:
            maximum_profit_achieved = potential_profit_today

    return maximum_profit_achieved

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	The solution should gracefully handle this by returning 0 profit, as no transaction is possible.
Array with only one element	Since a buy and sell must be on different days, a single element array means no transaction is possible, resulting in 0 profit.
Array with prices strictly decreasing	The algorithm should correctly identify that no profit can be made and return 0.
Array with prices strictly increasing	The algorithm should identify the first day as the buy day and the last day as the sell day to maximize profit.
Array with all identical prices	No profit can be made, so the algorithm should correctly return 0.
Large input array	The solution's linear time complexity ensures efficient handling of large inputs without performance degradation.
Prices containing zero or negative values	The problem statement implies stock prices are non-negative, but if they were allowed, the algorithm would still function correctly by finding the maximum difference.
Maximum possible profit leading to integer overflow	Using a data type that can accommodate the maximum possible profit, such as a 64-bit integer, prevents overflow issues.

Empty or null input array

How to Handle:

The solution should gracefully handle this by returning 0 profit, as no transaction is possible.

Array with only one element

How to Handle:

Since a buy and sell must be on different days, a single element array means no transaction is possible, resulting in 0 profit.

Array with prices strictly decreasing

How to Handle:

The algorithm should correctly identify that no profit can be made and return 0.

Array with prices strictly increasing

How to Handle:

The algorithm should identify the first day as the buy day and the last day as the sell day to maximize profit.

Array with all identical prices

How to Handle:

No profit can be made, so the algorithm should correctly return 0.

Large input array

How to Handle:

The solution's linear time complexity ensures efficient handling of large inputs without performance degradation.

Prices containing zero or negative values

How to Handle:

The problem statement implies stock prices are non-negative, but if they were allowed, the algorithm would still function correctly by finding the maximum difference.

Maximum possible profit leading to integer overflow

How to Handle:

Using a data type that can accommodate the maximum possible profit, such as a 64-bit integer, prevents overflow issues.

0/4 Toast questions completed

0/4 completed