algoadvance

Leetcode 122. Best Time to Buy and Sell Stock II

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 the maximum profit you can achieve.

Clarifying Questions

  1. Can transactions be made multiple times? Yes, you can buy and sell multiple times but can hold at most one share at a time.

  2. Are there any transaction fees? No, there are no transaction fees.

  3. Can we engage in multiple transactions in a single day? Yes, you can buy and sell on the same day.

Strategy

To maximize the profit, you should consider gaining profit from every increase in stock price from one day to the next. You can effectively create a strategy by summing up all the positive differences between each consecutive pair of days. This approach works because buying on the local low and selling on the local high within any time frame will always yield the optimal profit.

Steps:

  1. Initialize a variable maxProfit to store the accumulated profit.
  2. Iterate through the prices array from the second day onwards.
  3. For each day, compare the price with the previous day’s price.
  4. If today’s price is higher than yesterday’s price, add the difference (today’s price - yesterday’s price) to maxProfit (since this denotes a profit opportunity).
  5. Return the total maxProfit.

Code

public class BestTimeToBuyAndSellStockII {

    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;
    }

    public static void main(String[] args) {
        BestTimeToBuyAndSellStockII solution = new BestTimeToBuyAndSellStockII();
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(solution.maxProfit(prices)); // Output: 7
    }
}

Time Complexity

The time complexity is (O(n)), where (n) is the number of elements in the prices array, because we only need to iterate through the array once.

The space complexity is (O(1)) since we are using a constant amount of extra space regardless of the input size.

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