Leetcode 122. Best Time to Buy and Sell Stock II

Problem

Leetcode 122 - Best Time to Buy and Sell Stock II

Example:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Approach

We can simply get the max profit by simply taking a greedy approach where if next day is higher than current day, then we can just add the difference into the profit.

Visualization of the Approach:

nums = [7, 1, 5, 3, 6, 4]

start = 7
next_day = 1
Since next_day price is lower we don't add the profit
profit = 0

start = 1
next_day = 5
Since next_day price is higher we add the difference 
profit = 4

start = 5
next_day = 3
Since next_day price is lower we don't add the profit
profit = 4

start = 3
next_day = 6
Since next_day price is higher we add the difference
profit = 4 + 3

start = 6
next_day = 4
Since next_day price is lower we don't add the profit
profit = 4 + 3

Thus, the profit is 7

Here is the Python code for the solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        
        for i in range(1, len(prices)):
            # if next_day price is bigger than current day we add profit
            if prices[i] > prices[i-1]:
                profit += prices[i] - prices[i-1]
        
        return profit

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$