Best Time to Buy and Sell Stock II medium

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

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.

Steps:

  1. Iterate through the prices array: We'll traverse the array from left to right.
  2. Identify price increases: For each day, we check if the price is higher than the previous day's price.
  3. Accumulate profit: If the current price is higher, we add the difference (profit) to our total profit.

Explanation:

The key insight to solving this problem efficiently is that we don't need to track individual buy and sell points. We only care about the differences in price between consecutive days. If the price goes up, we can make a profit. If the price goes down, we simply skip that day (we wouldn't buy at a high price and sell at a lower price). This approach effectively sums up all the profitable increases in price.

Code:

function maxProfit(prices: number[]): number {
    let profit: number = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
};

Complexity:

  • Time Complexity: O(n), where n is the number of prices. We iterate through the array once.
  • Space Complexity: O(1). We use only a constant amount of extra space to store the profit variable.