Best Time to Buy and Sell Stock II LeetCode Solution

Last updated on July 13th, 2024 at 04:45 am

Here, We see Best Time to Buy and Sell Stock II Leetcode Solution. With different approaches, this Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Dynamic Programming, Greedy

Companies

Bloomberg

Level of Question
Best Time to Buy and Sell Stock II LeetCode Solution

Best Time to Buy and Sell Stock II LeetCode Solution

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.

Example 1:
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.

Example 2:
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.

Example 3:
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.

1. Best Time to Buy and Sell Stock II Leetcode Solution C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0, profit = 0, buy, sell;
        while (i < prices.size() - 1) {
            while (i < prices.size() - 1 && prices[i + 1] <= prices[i]) {
                i++;
            }
            buy = prices[i];
            while (i < prices.size() - 1 && prices[i + 1] > prices[i]) {
                i++;
            }
            sell = prices[i];
            profit += sell - buy;
        }
        return profit;
    }
};

1.1 Explanation

  1. Initialize i, profit, buy, and sell.
  2. Loop while i is less than the second-last index of prices.
  3. Find the next local minimum (buying point) by incrementing i while the next day’s price is less than or equal to the current day’s price.
  4. Store the buying price.
  5. Find the next local maximum (selling point) by incrementing i while the next day’s price is greater than the current day’s price.
  6. Store the selling price.
  7. Calculate the profit for this transaction and add it to the total profit.
  8. Return the total profit.

1.2 Time Complexity

  • Worst-case: O(n), where n is the number of elements in prices. Each element is processed once in a linear scan.

1.3 Space Complexity

  • O(1), as only a fixed amount of extra space is used.

2. Best Time to Buy and Sell Stock II Leetcode Solution Java

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

2.1 Explanation

  1. Initialize maxprofit to 0.
  2. Loop from the second element to the end of prices.
  3. If the current price is greater than the previous price, add the difference to maxprofit.
  4. Return maxprofit.

2.2 Time Complexity

  • O(n), where n is the length of prices.

2.3 Space Complexity

  • O(1), as no extra space is used except for a few variables.

3. Best Time to Buy and Sell Stock II Leetcode Solution JavaScript

var maxProfit = function(prices) {
    let profits = [0]; // base condition
    
    for(let i = 1; i < prices.length; i++) {
        profits[i] = profits[i - 1] + Math.max(0, prices[i] - prices[i - 1]);
    }
    
    return profits.pop();
};

3.1 Explanation

  1. Initialize profits array with a single element 0.
  2. Loop from the second element to the end of prices.
  3. For each element, calculate the profit if the price increased from the previous day and store the cumulative profit in profits.
  4. Return the last element of the profits array.

3.2 Time Complexity

  • O(n), where n is the length of prices.

3.3 Space Complexity

  • O(n), due to the use of the profits array.

4. Best Time to Buy and Sell Stock II Leetcode Solution Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit

4.1 Explanation

  1. Initialize profit to 0.
  2. Loop from the second element to the end of prices.
  3. If the current price is greater than the previous price, add the difference to profit.
  4. Return profit.

4.2 Time Complexity

  • O(n), where n is the length of prices.

4.3 Space Complexity

  • O(1), as only a fixed amount of extra space is used.
Scroll to Top