"None is not valid value for the expected return type" error for "Best time to buy and sell" challenge

Question

I am trying to solve LeetCode problem 121. 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 i^th 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.

Example 1:

Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

I wrote the following code in PyCharm and it worked perfectly without any errors, but when I ran it on LeetCode's console, it showed me a runtime error:

TypeError: None is not valid value for the expected return type integer
    raise TypeError(str(ret) + " is not valid value for the expected return type integer");
Line 46 in _driver (Solution.py)
    _driver()
Line 53 in <module> (Solution.py)
During handling of the above exception, another exception occurred:
TypeError: '<' not supported between instances of 'int' and 'NoneType'
Line 14 in _serialize_int (./python3/__serializer__.py)
Line 63 in _serialize (./python3/__serializer__.py)
    out = ser._serialize(ret, 'integer')
Line 44 in _driver (Solution.py)

Here is my code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        temp = prices
        nprofit = temp[0]

        for j in range(len(temp) - 1):
            if temp[j] > temp[j + 1]:
                nprofit = temp[j]

        if nprofit == temp[len(temp) - 1]:
            return 0
        else:
            for i in range(len(temp)):
                smallest = min(temp)

                if temp.index(smallest) == len(temp) - 1:
                    temp.remove(smallest)
                else:
                    largest = max(temp[temp.index(smallest) + 1:])
                    print(largest - smallest)
                    profit = largest - smallest
                    return int(profit)

The above code is giving me the correct output on PyCharm and also gives the correct output of the print statement in the stdout on the LeetCode console.

What is my mistake?

Answer 1

The problem occurs when the input is a descending list of prices, like [3,2,1]. This means the if condition is true in every iteration of your for i loop, and each time the last entry of the list is removed. As the else block never gets to execute, the loop ends, and there is nothing you have to return there, and so None is returned. But the function should always return an int. The error message you got highlights that.

In this particular case (of descending prices), you should follow this instruction given in the code challenge:

If you cannot achieve any profit, return 0.

And so the fix for this particular problem is to add a return 0 at the end of the else block.

More problems

But even if the input is not descending like described above, your approach to find the least value and then take the greatest that follows it, is not always the right one. Take for instance the input [2,5,1,3]. Your algorithm would select 1 and offset it against 3, giving a profit of 2. But a better profit is achieved with the pair 2, 5.

You need a better algorithm all together. Back to the drawing board...

Solution

A solution is to use a running minimum, i.e. the minimum value encountered so far. Compare this running minimum with the current value to see if it beats the best profit so far.

A spoiler in case you cannot make it to work:

class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 low = prices[0] for price in prices: if price < low: low = price elif price - low > profit: profit = price - low return profit