DSA 450 Notes

Problem Statement

Given an array of stock prices where the i-th element is the price of a given stock on day i, find the maximum profit you can achieve by making at most two transactions. You must sell the stock before you buy again.

Example:

Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 3. Total profit = 6.

Approach 1: Brute Force

Intuition

Try all possible combinations of two transactions. For each possible split point, calculate the maximum profit from the left part and right part independently.

Algorithm

For each split point i from 0 to n-1
Calculate max profit from [0, i] (first transaction)
Calculate max profit from [i, n-1] (second transaction)
Track the maximum combined profit

java

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        
        int maxTotalProfit = 0;
        
        // Try all split points
        for (int i = 0; i < n; i++) {
            // Max profit from first transaction [0, i]
            int profit1 = 0;
            int minPrice = prices[0];
            for (int j = 1; j <= i; j++) {
                minPrice = Math.min(minPrice, prices[j]);
                profit1 = Math.max(profit1, prices[j] - minPrice);
            }
            
            // Max profit from second transaction [i, n-1]
            int profit2 = 0;
            minPrice = prices[i];
            for (int j = i + 1; j < n; j++) {
                minPrice = Math.min(minPrice, prices[j]);
                profit2 = Math.max(profit2, prices[j] - minPrice);
            }
            
            maxTotalProfit = Math.max(maxTotalProfit, profit1 + profit2);
        }
        
        return maxTotalProfit;
    }
}

Complexity Analysis

Time Complexity: O(n²) - For each split point, we calculate profits in both halves
Space Complexity: O(1) - Only constant extra space used

Approach 2: Optimal - Precomputation with Two Arrays

Intuition

Precompute the maximum profit achievable from the left (ending at each day) and from the right (starting at each day). Then combine them to find the optimal split point.

Algorithm

Create leftProfit[i] = max profit from [0, i]
Create rightProfit[i] = max profit from [i, n-1]
Answer = max(leftProfit[i] + rightProfit[i]) for all i

java

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        
        // leftProfit[i] = max profit from [0, i]
        int[] leftProfit = new int[n];
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            leftProfit[i] = Math.max(leftProfit[i - 1], prices[i] - minPrice);
        }
        
        // rightProfit[i] = max profit from [i, n-1]
        int[] rightProfit = new int[n];
        int maxPrice = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            maxPrice = Math.max(maxPrice, prices[i]);
            rightProfit[i] = Math.max(rightProfit[i + 1], maxPrice - prices[i]);
        }
        
        // Find maximum combined profit
        int maxTotalProfit = 0;
        for (int i = 0; i < n; i++) {
            maxTotalProfit = Math.max(maxTotalProfit, leftProfit[i] + rightProfit[i]);
        }
        
        return maxTotalProfit;
    }
}

Complexity Analysis

Time Complexity: O(n) - Three linear passes through the array
Space Complexity: O(n) - Two arrays of size n

Approach 3: Optimal - State Machine (Constant Space)

Intuition

Track four states: after first buy, after first sell, after second buy, after second sell. Update all states in a single pass.

Algorithm

Track buy1, sell1, buy2, sell2
buy1 = max profit after first buy (negative value means cost)
sell1 = max profit after first sell
buy2 = max profit after second buy
sell2 = max profit after second sell

java

public class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, sell1 = 0;
        int buy2 = Integer.MIN_VALUE, sell2 = 0;
        
        for (int price : prices) {
            buy1 = Math.max(buy1, -price);           // Max profit after first buy
            sell1 = Math.max(sell1, buy1 + price);   // Max profit after first sell
            buy2 = Math.max(buy2, sell1 - price);    // Max profit after second buy
            sell2 = Math.max(sell2, buy2 + price);   // Max profit after second sell
        }
        
        return sell2;
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through the array
Space Complexity: O(1) - Only four variables used

Key Takeaways

Precomputation technique - Computing left and right arrays allows efficient combination
State machine approach - Tracking buy/sell states enables O(1) space solution
Can be generalized - The state machine approach extends to k transactions
Order matters - Must sell before buying again (no holding multiple stocks)

Maximum profit by buying and selling a share atmost twice

Problem Statement

Approach 1: Brute Force

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal - Precomputation with Two Arrays

Intuition

Algorithm

Complexity Analysis

Approach 3: Optimal - State Machine (Constant Space)

Intuition

Algorithm

Complexity Analysis

Key Takeaways