LeetCode 121. Best Time to Buy and Sell Stock

Problem Description

Difficulty: Easy

Given an array of prices where prices[i] indicates the cost of a specific asset on the i^th day. Optimize the returns by selecting one day to purchase the asset and a subsequent day to sell it. Determine the highest possible profit. If no profit can be made, return 0.

Example 1:

Input: prices = [8, 2, 4, 7, 3, 5]
Output: 5

Explanation: Buy on day 2 (price = 2) and sell on day 4 (price = 7); the profit is 7 - 2 = 5.

Example 2:

Input: prices = [9, 7, 6, 3, 1]
Output: 0

Explanation: No profitable transactions are possible, so the maximum profit is 0.

Initial Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l = 0  # buy-price pointer
        r = 0  # sell-price pointer
        max_profit = 0

        while r < len(prices):
            profit = prices[r] - prices[l]
            max_profit = max(max_profit, profit)
            if prices[l] > prices[r]:
                l += 1
            else:
                r += 1

        return max_profit

solution = Solution()
# Test cases
assert solution.maxProfit([8, 2, 4, 7, 3, 5]) == 5
assert solution.maxProfit([9, 7, 6, 3, 1]) == 0
assert solution.maxProfit([1, 2]) == 1
print("Tests completed")

Tests completed

Initial Results:

I addressed this problem with a two-pointer algorithm that is basically a variable sliding window. The above code beat 94% of LeetCode submissions on runtime and 97% on memory. This was somewhat surprising for my first attempt, so I took a screenshot (image below). Most submissions used a for loop, also in linear time, but presumably with some additional calculations within. I created another version with a for loop, which is likely a cleaner way of doing this, but the speed was about the same.

LeetCodeSubmission.png

Complexity

• Time complexity: \(O(n)\) as the pointers traverse the input list only once (l and r only increase and do not reset).
• Space complexity: \(O(1)\) as no additional space is used that would grow with input size.

NeetCode Solution

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

This solution also has \(O(n)\) time complexity. However, NeetCode’s is more elegant with fewer operations. On LeetCode, it ran in 74 ms and beat around 97% of submissions on time and space.

Interestingly, LeetCode’s youtube video has a different solution to that given on the website, without any explanation for the difference. It’s shown below and ran in 118 ms. It’s a little better than mine as the profit is only calculated when the price at l is less than the price at r, which avoids some unnecessary calculations. The l = r part, instead of l += 1, should allow it to skip ahead quicker too. I tried that out in my code above, and it didn’t seem to make much difference though.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r = 0, 1
        maxP = 0
        while r < len(prices):
            if prices[l] < prices[r]:
                profit = prices[r] - prices[l]
                maxP = max(maxP, profit)
            else:
                l = r
            r += 1
        return maxP