Jobs

Interviews

Discussions

Best Time to Buy and Sell Stock

Easy

Walmart

0 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⁴

Best Time to Buy and Sell Stock

Easy

Walmart

0 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⁴

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 of values for the stock prices (e.g., non-negative integers)?
What should I return if there is no possible profit (i.e., the prices are always decreasing or the array is empty)?
Is the input array guaranteed to have at least two elements?
Can I assume the 'i' in prices[i] represents consecutive days?
Are there any memory constraints I should be aware of, or is the primary concern optimizing for time complexity?

Brute Force Solution

Approach

The brute force way to solve this is to try every possible buy and sell combination. We check each possible day to buy the stock, and then for each of those days, we check every possible later day to sell the stock.

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

Consider each day as a potential day to buy the stock.
For each possible buying day, consider every day that comes after it as a potential day to sell the stock.
Calculate the profit for each of these buy/sell combinations (selling price minus buying price).
Keep track of the maximum profit you've found so far.
After checking all possible buy/sell combinations, the maximum profit you've kept track of is the answer.

Code Implementation

def best_time_to_buy_and_sell_stock_brute_force(prices):
    maximum_profit = 0

    # Iterate through all possible buying days
    for buying_day in range(len(prices)):

        # Iterate through all possible selling days after the buying day
        for selling_day in range(buying_day + 1, len(prices)):

            # Calculate the potential profit for this buy/sell combination
            potential_profit = prices[selling_day] - prices[buying_day]

            # Update maximum_profit if this profit is greater
            if potential_profit > maximum_profit:
                maximum_profit = potential_profit

    return maximum_profit

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iterates through each day (n days) as a potential buying day. For each buying day, it then iterates through all subsequent days to find a selling day. This means that for each of the n potential buying days, we iterate over roughly n remaining days to calculate profits. Thus, the total number of calculations grows proportionally to n multiplied by n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force solution only uses a single variable to keep track of the maximum profit found so far. No additional data structures, like arrays or hash maps, are created. The space used by this variable remains constant regardless of the size of the input array of prices (N). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The best strategy to maximize profit is to find the lowest price to buy and the highest price after that point to sell. We achieve this by keeping track of the lowest price we've seen so far and updating our maximum profit whenever we find a selling price that gives us a higher profit.

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

Start by assuming our best buying price is the very first price we see.
Also, assume our initial profit is zero because we haven't bought and sold anything yet.
Now, go through the rest of the prices one by one.
For each price, check if it's lower than our current best buying price. If it is, update our best buying price to this new lower price.
If the current price is not a new low, calculate the profit we would make if we sold at this price, using our current best buying price.
If this potential profit is greater than our current maximum profit, update our maximum profit.
Continue this process until we have considered all the prices.
The final maximum profit we have is the best profit we can achieve.

Code Implementation

def max_profit(prices):
    if not prices:
        return 0

    best_buying_price = prices[0]
    maximum_profit = 0

    for current_price in prices:
        # If we find a lower buying price, update it.
        if current_price < best_buying_price:

            best_buying_price = current_price

        # Otherwise, check to update max profit.
        else:
            potential_profit = current_price - best_buying_price
            #Keep track of the largest profit seen so far
            if potential_profit > maximum_profit:

                maximum_profit = potential_profit

    # Return the maximum profit found
    return maximum_profit

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of prices once. For each price, it performs a constant amount of work: comparing it to the current minimum buying price and updating the maximum profit if necessary. The cost is directly proportional to the number of prices, n, where n is the length of the input array. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses two variables, best_buying_price and maximum_profit, to store the best buying price seen so far and the maximum profit achieved. The space occupied by these variables remains constant irrespective of the input array's size N (number of prices). Therefore, the auxiliary space complexity is O(1), indicating constant space usage.

Edge Cases

Case	How to Handle
Empty input array	Return 0, as no profit can be made with no prices.
Input array with only one element	Return 0, as buying and selling on the same day yields no profit.
Input array with prices in strictly decreasing order	Return 0, as no profitable transaction is possible.
Input array with all prices being the same	Return 0, as no change in price allows for any profit.
Large input array (scalability)	The algorithm should use O(n) time complexity for optimal performance with large inputs.
Input array contains very large price values leading to potential integer overflow	Use a data type that can accommodate larger values (e.g., long) or handle potential overflow explicitly.
Input array with negative price values	The problem doesn't explicitly state that prices cannot be negative; algorithm should handle them correctly by calculating the maximum profit even with negative prices.
Prices array contains zeros	The presence of zero in prices should not affect the logic as it would be treated as a regular price point.

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 of values for the stock prices (e.g., non-negative integers)?
What should I return if there is no possible profit (i.e., the prices are always decreasing or the array is empty)?
Is the input array guaranteed to have at least two elements?
Can I assume the 'i' in prices[i] represents consecutive days?
Are there any memory constraints I should be aware of, or is the primary concern optimizing for time complexity?

Brute Force Solution

Approach

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

Consider each day as a potential day to buy the stock.
For each possible buying day, consider every day that comes after it as a potential day to sell the stock.
Calculate the profit for each of these buy/sell combinations (selling price minus buying price).
Keep track of the maximum profit you've found so far.
After checking all possible buy/sell combinations, the maximum profit you've kept track of is the answer.

Code Implementation

def best_time_to_buy_and_sell_stock_brute_force(prices):
    maximum_profit = 0

    # Iterate through all possible buying days
    for buying_day in range(len(prices)):

        # Iterate through all possible selling days after the buying day
        for selling_day in range(buying_day + 1, len(prices)):

            # Calculate the potential profit for this buy/sell combination
            potential_profit = prices[selling_day] - prices[buying_day]

            # Update maximum_profit if this profit is greater
            if potential_profit > maximum_profit:
                maximum_profit = potential_profit

    return maximum_profit

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by assuming our best buying price is the very first price we see.
Also, assume our initial profit is zero because we haven't bought and sold anything yet.
Now, go through the rest of the prices one by one.
For each price, check if it's lower than our current best buying price. If it is, update our best buying price to this new lower price.
If the current price is not a new low, calculate the profit we would make if we sold at this price, using our current best buying price.
If this potential profit is greater than our current maximum profit, update our maximum profit.
Continue this process until we have considered all the prices.
The final maximum profit we have is the best profit we can achieve.

Code Implementation

def max_profit(prices):
    if not prices:
        return 0

    best_buying_price = prices[0]
    maximum_profit = 0

    for current_price in prices:
        # If we find a lower buying price, update it.
        if current_price < best_buying_price:

            best_buying_price = current_price

        # Otherwise, check to update max profit.
        else:
            potential_profit = current_price - best_buying_price
            #Keep track of the largest profit seen so far
            if potential_profit > maximum_profit:

                maximum_profit = potential_profit

    # Return the maximum profit found
    return maximum_profit

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0, as no profit can be made with no prices.
Input array with only one element	Return 0, as buying and selling on the same day yields no profit.
Input array with prices in strictly decreasing order	Return 0, as no profitable transaction is possible.
Input array with all prices being the same	Return 0, as no change in price allows for any profit.
Large input array (scalability)	The algorithm should use O(n) time complexity for optimal performance with large inputs.
Input array contains very large price values leading to potential integer overflow	Use a data type that can accommodate larger values (e.g., long) or handle potential overflow explicitly.
Input array with negative price values	The problem doesn't explicitly state that prices cannot be negative; algorithm should handle them correctly by calculating the maximum profit even with negative prices.
Prices array contains zeros	The presence of zero in prices should not affect the logic as it would be treated as a regular price point.