Interview Sheet Q2:- 121. Best Time to Buy and Sell Stock

Approach 1: Brute Force

• Try every possible buy day.
• For each buy day, try every sell day after it.
• Calculate profit and keep maximum.

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;

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

        return maxProfit;
    }
}

Complexity

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

Approach 2: Optimal One Pass

• Keep track of minimum price seen so far.

• At every index:

  • Calculate profit if sold today.
  • Update maximum profit.

• If current price is smaller, update minimum buy price.

Example:

Buy at 1
Sell at 6
Profit = 5

class Solution {
    public int maxProfit(int[] prices) {

        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {

            minPrice = Math.min(minPrice, price);

            int profit = price - minPrice;

            maxProfit = Math.max(maxProfit, profit);
        }

        return maxProfit;
    }
}

Complexity

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