Best time to Buy and Sell Stock II

Problem Link

Best Time to Buy and Sell Stock II – LeetCode

Problem: 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 stock on the iᵗʰ day.

You may buy and/or sell the stock on each day, but you can only hold at most one share of the stock at any time. However, you can buy and sell on the same day.

Return the maximum profit you can achieve.

Examples

Example 1
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation:

• Buy at 1, sell at 5 → Profit = 4

• Buy at 3, sell at 6 → Profit = 3

• Total Profit = 4 + 3 = 7

Example 2
Input: prices = [1,2,3,4,5]
Output: 4
Explanation:

• Buy at 1, sell at 5 → Profit = 4

• Or buy-sell every day with increasing price → Same total profit

Example 3
Input: prices = [7,6,4,3,1]
Output: 0
Explanation:

• Prices are decreasing. No transactions are profitable.

Constraints

• 1 <= prices.length <= 3 × 10⁴

• 0 <= prices[i] <= 10⁴

Intuition

The problem allows multiple transactions as long as we don’t hold more than one stock at a time. Hence, every time the price increases from one day to the next, we can buy on the previous day and sell on the current day to gain profit.

Approach

1. Initialize maxProfit as 0.

2. Traverse the prices array starting from index 1.

3. If prices[i] > prices[i-1], that means a profit can be made.

4. Add prices[i] - prices[i-1] to maxProfit.

5. Continue this till the end and return maxProfit.

This greedy approach ensures that we capture all profitable trades.

Code (Java)

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

Time and Space Complexity

• Time Complexity: O(n)
  We iterate through the array once.

• Space Complexity: O(1)
  Only a single variable is used to track profit.

Dry Run

Input: prices = [7,1,5,3,6,4]

• Day 1: 1 < 7 → No profit

• Day 2: 5 > 1 → Profit = 4 → Total = 4

• Day 3: 3 < 5 → No profit

• Day 4: 6 > 3 → Profit = 3 → Total = 7

• Day 5: 4 < 6 → No profit

Output: 7

Conclusion

This problem is a classic example of greedy algorithms in action. Since transactions are unlimited, we simply capitalize on every local increase to maximize our profit efficiently.