Best Time to Buy and Sell Stock algorithm and solutions in Java and Python - Kadane Algo

The “Best Time to Buy and Sell Stock” problem is one of the most common Kadane’s Algorithm variations (used for maximum subarray sum problems) and can also be thought of as a sliding window or one-pass optimization problem.

Let’s break it down thoroughly 👇

---

🧩 Problem Statement

You are given an array prices[] where prices[i] is the price of a stock on the i-th day. You want to maximize your profit by choosing a single day to buy and a different day to sell.

You can only make one transaction (buy once, sell once).

Return the maximum profit. If no profit can be made, return 0.

---

Example:

Input:  prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price=1) and sell on day 5 (price=6)
Profit = 6 - 1 = 5

---

🧠 1. Brute Force (O(n²))

Try all pairs (buy, sell) and calculate profit.

Java:

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

Python:

def max_profit_brute(prices):
    max_profit = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    return max_profit

🕒 Time: O(n²) 💾 Space: O(1)

---

⚡ 2. Optimized Approach (O(n)) — Kadane’s Variation / Sliding Window

🔍 Intuition:

We want the maximum difference prices[j] - prices[i], where j > i. To do this efficiently:

• Keep track of the minimum price so far (minPrice)
• For each price, calculate the potential profit = price - minPrice
• Update the maxProfit whenever this profit is greater

This is essentially a Kadane’s-style running maximum difference.

---

✅ Java Solution:

public class BestTimeToBuySellStock {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            // update minimum price seen so far
            if (price < minPrice)
                minPrice = price;
            // calculate profit if sold today
            else if (price - minPrice > maxProfit)
                maxProfit = price - minPrice;
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Max Profit: " + maxProfit(prices)); // 5
    }
}

---

✅ Python Solution:

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price

    return max_profit

# Example
prices = [7,1,5,3,6,4]
print(max_profit(prices))  # Output: 5

🕒 Time: O(n) 💾 Space: O(1)

---

🧭 3. Kadane’s Algorithm Perspective

If you transform the prices array into daily profit/loss changes, i.e., diff[i] = prices[i] - prices[i-1], then finding the maximum profit becomes identical to finding the maximum subarray sum — which is exactly Kadane’s Algorithm.

---

Example:

prices = [7,1,5,3,6,4]
diffs  = [   -6,4,-2,3,-2]

Now apply Kadane’s:

• Keep track of currentSum and maxSum
• currentSum = max(0, currentSum + diff[i])
• maxSum = max(maxSum, currentSum)

Final maxSum = 5

---

✅ Python (Kadane’s form)

def max_profit_kadane(prices):
    max_curr = 0
    max_profit = 0
    for i in range(1, len(prices)):
        diff = prices[i] - prices[i-1]
        max_curr = max(0, max_curr + diff)
        max_profit = max(max_profit, max_curr)
    return max_profit

---

🚀 4. Sliding Window Interpretation

You can think of this as a moving window:

• The left pointer marks the best “buy day”.
• The right pointer moves forward as you “sell”.
• If prices[right] < prices[left], move the window (buy cheaper).

---

✅ Python Sliding Window

def max_profit_sliding_window(prices):
    left = 0   # buy day
    max_profit = 0
    for right in range(1, len(prices)):
        if prices[right] < prices[left]:
            left = right
        else:
            profit = prices[right] - prices[left]
            max_profit = max(max_profit, profit)
    return max_profit

---

📊 Summary Table

Approach	Concept	Time	Space	Notes
Brute Force	Compare all pairs	O(n²)	O(1)	Simple, slow
One-Pass	Track min & profit	O(n)	O(1)	Most common
Kadane’s	Max subarray on diffs	O(n)	O(1)	Elegant math link
Sliding Window	Two pointers	O(n)	O(1)	Intuitive visualization

---

🏦 Real-World Analogy

Imagine watching stock prices daily. You want to:

• Buy at the lowest valley
• Sell at the next highest peak
• Maximize your gain in a single transaction

This pattern also applies to:

• Commodity trading (gold, oil, etc.)
• Predicting peak network traffic reduction (min/max deltas)
• Profit/loss trend analysis over time

---