max() arg is an empty sequence when solving Best Time To Buy and Sell Stock

Question

I'm working on a Leetcode problem called "Best Time to Buy and Sell Stock".

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Constraints:

1 <= prices.length <= 10**5

0 <= prices[i] <= 10**4

This is my solution:

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

I tested all cases on my IDE (VS Code) and it all passes. But, I got the error shown below when I submitted it on LeetCode. What's wrong with my code?

ValueError: max() arg is an empty sequence
    if max(res) <= 0:

Answer 1

LeetCode tells you that the constraint on prices is:

1 <= prices.length <= 10**5

If prices.length == 1, then the inner part of your for loop will never fire, causing res to be an empty list.

One fix is to add an if guard at the top of your function, since you can't sell the stock on a different day if there's only one day to buy or sell:

def maxProfit(self, prices: List[int]) -> int:
    if len(prices) == 1:
         return 0

---

However, the runtime is quadratic in the length of the prices list, and with up to 10**5 days to consider, your approach will time out, even after adding the if guard.

Here is a linear time approach: essentially, for each day, you want to compute the cheapest stock price seen before that day and the most expensive stock price seen after that day. This allows you to only consider buy-sell possibilities that are feasible (i.e. they meet the constraint that you must buy a stock before you sell it.) The following code will pass LeetCode's test cases.

import math
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_prices = [0] * len(prices)
        max_prices = [0] * len(prices)
        
        min_price = math.inf
        max_price = 0
        for i in range(len(prices)):
            min_price = min(min_price, prices[i])
            min_prices[i] = min_price
            
        for i in range(len(prices) - 1, -1, -1):
            max_price = max(max_price, prices[i])
            max_prices[i] = max_price
        
        result = 0
        for minimum, maximum in zip(min_prices, max_prices):
            result = max(maximum - minimum, result)
        return result