algoadvance

Leetcode 122. Best Time to Buy and Sell Stock II

Problem Statement

The problem is to determine the maximum profit that can be achieved from an array where each element represents the price of a stock on a given day. You are allowed to buy and sell the stock multiple times, but you must sell the stock before you buy again.

Clarifying Questions

  1. Input Constraints: What is the range of stock prices and the number of days considered?
    • Stock prices are non-negative integers, and the number of days can vary widely, depending on the specific problem input.
  2. Multiple Buys/Sells: Are there any restrictions on the number of transactions we can make?
    • You can make as many transactions as necessary to maximize profit.
  3. Transaction Costs: Are there any transaction costs or limitations we should consider?
    • No, there are no transaction costs or limitations mentioned.
  4. Edge Cases: What about edge cases like an empty array or single-element array?
    • If the array is empty or contains only one element, no transactions can occur, so the profit is zero.

Strategy

To solve this problem, we employ a greedy algorithm. The idea is to accumulate profit by capturing all increases across consecutive days. We can achieve this by iterating through the array and summing up all profitable differences (i.e., prices[i+1] - prices[i] if it results in a gain).

Code

#include <vector>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        int maxProfit = 0;
        for (size_t i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
};

Time Complexity

The time complexity for this solution is (O(n)) where (n) is the number of days (or the length of the prices array). This is because we only iterate through the array once.

Explanation

  1. Initialization: We start with an initial maxProfit of 0.
  2. Iteration: Iterate through the prices array starting from the second day:
    • If the price of the current day (prices[i]) is greater than the price of the previous day (prices[i-1]), we add the difference to maxProfit.
  3. Return Result: The accumulated maxProfit at the end of the iteration gives the result.

This greedy approach ensures that we capture all profitable transactions without explicitly tracking buy/sell operations but rather focusing directly on profitable increments.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI