Best Time To Buy And Sell Stock - Leetcode Solution

The Best Time to Buy and Sell Stock problem on LeetCode asks us to find the maximum profit that can be made by buying and then selling a stock with the given prices. In other words, we need to find the difference between the maximum price and the minimum price in the given array of stock prices.

We can solve this problem efficiently by iterating over the price array and keeping track of the minimum price seen so far and the maximum profit that can be made by buying at that minimum price and selling at the current price. We update the maximum profit at each iteration and return it as the final result.

Here is the step by step algorithm to solve this problem:

1. Initialize the minimum price and maximum profit to the first price in the array.
2. Iterate over the remaining prices in the array: a. If the current price is less than the minimum price seen so far, update the minimum price. b. Otherwise, calculate the profit that can be made by buying at the minimum price seen so far and selling at the current price. If this profit is greater than the maximum profit seen so far, update the maximum profit.
3. Return the maximum profit as the final result.

Here is the Python code implementation of the above algorithm:

def maxProfit(prices):
    if len(prices) < 2:
        return 0
        
    min_price = prices[0]
    max_profit = 0
    
    for price in prices[1:]:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)
            
    return max_profit

In this code, we first handle the edge case where the length of the given price array is less than 2. If the input array has only one or no prices, we cannot make any profit, so we return 0.

If we have more than one price in the array, we initialize the minimum price to the first price and the maximum profit to 0. Then we iterate over the remaining prices in the array and update the minimum price and maximum profit at each iteration as described in the algorithm above.

Finally, we return the maximum profit as the result.

The time complexity of this algorithm is O(n) where n is the length of the input array, and the space complexity is O(1) since we only need to store the minimum price and maximum profit.

1