Friedrich Ewald My Personal Website

Leetcode: Best time to buy and sell stock

The task is to find out of a series of stock prices the best time to buy and sell the stock. Only one stock can be owned at the time and it can be sold and bought at the same time. The Python solution looks like this. It’s not entirely optimal because technically we could sell stock at every transaction, which simplifies the code as shown below. 

from typing import List

class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    profit = 0
    buy = -1
    for i in range(len(prices) - 1):
      if buy == -1:
        if prices[i] < prices[i + 1]:
          buy = prices[i]
      else:
        if prices[i] > prices[i+1]:
          profit += (prices[i] - buy)
          buy = -1
    if buy > -1:
      profit += prices[-1] - buy
    return profit

if __name__ == '__main__':
  r = Solution().maxProfit
  print(r([7,1,5,3,6,4]), 7)
  print(r([1,2,3,4,5]), 4)
  print(r([7,6,4,3,1]), 0)
Now the same code in Python but always sell: 
class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    profit = 0
    buy = -1
    for i in range(len(prices) - 1):
      # See if I can sell
      if buy > -1:
        profit += (prices[i] - buy)
        buy = -1
    
      # See if I should buy again
      if prices[i] < prices[i + 1]:
        buy = prices[i]
      
    if buy > -1:
      profit += prices[-1] - buy
    return profit
And the same in Go, solved some years ago. 
func maxProfit(prices []int) int {
  profit := 0
  ownStock := false
  lastPrice := prices[0]
  boughtAt := 0

  for i := 1; i < len(prices); i++ {
    currPrice := prices[i]
    if ownStock {
      // Check if should sell
      if currPrice < lastPrice {
        profit += lastPrice - boughtAt
        ownStock = false
      }
    } else {
      // Check if should buy
      if currPrice > lastPrice {
        boughtAt = lastPrice
        ownStock = true
      }
    }
    lastPrice = currPrice
  }

  // Sell at the end
  if ownStock {
    profit += prices[len(prices)-1] - boughtAt
  }

  return profit
}
The code itself is not that interesting once the idea is understood. What I found remarkable however, is the speed at which the code gets executed. The Go solution is by far the fastest, taking only 4ms. The second fastest solution is the first (and less clean) solution to keep the stock as long as possible with 88ms runtime. The slowest solution is the Python solution that sells the stock immediately with 115ms.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts