Best Time to Buy and Sell Stock II LeetCode

Key takeaways
The Best Time to Buy and Sell Stock II problem aims to maximize profits from stock trading over multiple days, allowing for multiple buy/sell transactions.
You can hold only one share of stock at any time and buy/sell on the same day.
The approach to solving this problem involves iterating through the price list, capturing profits whenever the current day's price exceeds the previous day's price. Add the difference between consecutive days' prices to a running total of profit whenever a profitable opportunity is identified.
The time complexity is $O(n)$ , where n is the length of the prices array.
The space complexity is $O(1)$ .

This a classic algorithmic challenge that tests our ability to maximize profits from stock trading over a series of days. Unlike the simpler version, where we can only make one transaction (buy and sell once), this problem allows for multiple transactions (buy and sell multiple times). Only one share can be held of the stock at any time is the key constraint of this problem.

Problem statement

We have an array of integers, prices, where prices[i] represents the price of a particular stock on the $i^{th}$ day. Each day, we can choose to buy and/or sell the stock, but we can only hold one share of the stock at any given time. We also have the option to buy and sell the stock on the same day.

Determine and return the maximum profit we can achieve.

Constraints

$1$ $\leq$ prices.length $\leq$ $10 ^ 3$
$0$ $\leq$ prices[i] $\leq$ $10^4$

Let’s gain a better understanding of the problem with the following examples:

Solution

To solve this problem, we can use a simple idea to capture all the profitable opportunities by considering every upward price movement as a potential profit. The algorithm walks through the following steps:

We initialize a variable, profit, with $0$ , to keep track of the total profit.
We start iterating from the second day of the prices list, and in each iteration, we perform the following steps:
1. We compare the price of each day with the price of the previous day.
2. If the price of the current day is higher than the price of the previous day, it means there is an opportunity to buy the stock on the previous day and make a profit, and then sell it on the current day.
3. We add the difference between the price of the current day and the price of the previous day to profit.
We return the total profit stored in profit.

This approach ensures that we capture all the small profits that add up to the maximum possible profit. Let’s look at the following illustration for a better understanding.

def maxProfit(prices):
    # Initialize the total profit with 0
    profit = 0
    # Traverse the list of prices
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            # Determine the profit from buying on previous day and selling on current day
            profit += prices[i] - prices[i - 1]
    return profit
def main():
  pricesList = [[7,1,5,3,6,4], 
    [1,7,2,8,4,9], 
    [8, 3, 5, 2, 4, 6, 0, 1], 
    [2,3,4,5,6], 
    [7,6,4,3,1]
  ]
  i = 1
  for x in pricesList:
    print(i, ".\tPrices: ", x, sep = "")
    print("\n\tProfit: ", maxProfit(x), sep = "")
    print("-"*100, "\n", sep = "")
    i+=1
if __name__ == "__main__":
    main()

Best Time to Buy and Sell Stock II Leetcode

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Best Time to Buy and Sell Stock II LeetCode

Problem statement

Knowledge test

Solution

Coding example

Time complexity

Space complexity