LeetCode 121. Best Time to Buy and Sell Stock

Description

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

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Explanation

The problem is seeking the max profit in buying and selling stocks.

This is a simple modeling stocks trading in real life. The essence of the problem is looking for the max value of prices[i2] – prices[i1], i2 > i1.

prices[i2] is the max value in the array. prices[i1] is the minimum value in the array.

It’s easy to solve the problem by keep tracking of the minimum price and max profit when iterating the array.

Java Solution

public class Solution { 
    public int maxProfit(int[] prices) { 
        int maxProfit = 0; 
        int minPrice = Integer.MAX_VALUE; 
        for (int i = 0; i < prices.length; i++) { 
            minPrice = Math.min(minPrice, prices[i]); 
            maxProfit = Math.max(maxProfit, prices[i] - minPrice); 
        } 
        return maxProfit; 
    } 
}


Python Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        max_profit = 0
        if prices == None or len(prices) == 0:
            return max_profit
        
        min_price = prices[0]
        
        for price in prices[1:]:            
            profit = price - min_price
            max_profit = max(max_profit, profit)
            min_price = min(min_price, price)
            
        
        return max_profit
  • Time complexity: O(n).
  • Space complexity: O(1).

One Thought to “LeetCode 121. Best Time to Buy and Sell Stock”

Leave a Reply

Your email address will not be published. Required fields are marked *