LeetCode #121: Best Time to Buy and Sell Stock

LeetCode Solutions

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

To solve this problem in Python 3, we can use a simple approach that involves keeping track of the minimum price seen so far and the maximum profit that can be made by selling on the current day.

Here are the steps to follow:

  1. Initialize the minimum price as the first element of the array and the maximum profit as 0.
  2. Iterate through the array and for each element, update the minimum price seen so far and calculate the maximum profit that can be made by selling on the current day.
  3. If the current profit is greater than the maximum profit seen so far, update the maximum profit.
  4. Return the maximum profit.

Here’s the Python 3 code that implements this approach:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price
        return max_profit

In this code, we initialize the min_price variable to a large number (float('inf')) and the max_profit variable to 0. We then iterate through the prices array and for each element, we update the min_price variable if we encounter a smaller price and calculate the maximum profit that can be made by selling on the current day. If the current profit is greater than the maximum profit seen so far, we update the max_profit variable. Finally, we return the max_profit.

Time and Space Complexity:

The time complexity of this solution is O(n), where n is the length of the prices array. This is because we need to iterate through the array once to calculate the maximum profit.

The space complexity of this solution is O(1), because we are using constant space to store the min_price and max_profit variables, regardless of the size of the prices array.