[LeetCode Solution] 121. Best Time to Buy and Sell Stock

Problem Description

Best Time to Buy and Sell Stock

Calculate the maximum profit that can be obtained by buying and selling stocks once.

Solution

Approach

To find the maximum profit when buying and selling stocks once, we need to calculate the difference between the lowest and highest points in the stock prices. Since the given list is in chronological order, we need to consider this while iterating through the prices.

The algorithm is straightforward, and I’ll explain it directly in code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0                # Initial profit is 0
        lower = 100000            # Set the initial lowest point to the largest value in the given test cases.
        for v in prices:
            if v < lower:         # Update the lowest point
                lower = v
            if v - lower > 0 and profit < v - lower:    # If the difference between the current value and the lower point is greater than the current profit, update the profit.
                profit = v - lower
        return profit             # The remaining profit after the last loop is the maximum profit.

The time complexity and space complexity of this solution are as follows:

• Time Complexity: O(N)
  • As the loop iterates through prices, the time complexity is O(N).
• Space Complexity: O(1)
  • No additional space is used.