Best Time to Buy and Sell Stock

Problem Statement

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Examples

Example 1:

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. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.

Approaches

1. Brute Force Approach

The brute force approach involves checking every possible pair of buy and sell days to find the maximum profit.

Time Complexity: O(n^2), where n is the number of days Space Complexity: O(1)

2. Optimal Approach (One Pass)

The optimal approach uses a single pass through the array, keeping track of the minimum price seen so far and the maximum profit that can be achieved.

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

Solutions

Java Solution

// Brute Force Approach
class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }
}

// Optimal Approach (One Pass)
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }
}

C++ Solution

// Brute Force Approach
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.size() - 1; i++) {
            for (int j = i + 1; j < prices.size(); j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }
};

// Optimal Approach (One Pass)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }
};

Explanation

Brute Force Approach

Use two nested loops to consider every possible pair of buy and sell days.
For each pair, calculate the profit.
Keep track of the maximum profit seen so far.
Return the maximum profit after checking all pairs.

This approach is simple but inefficient for large inputs due to its O(n^2) time complexity.

Optimal Approach (One Pass)

This approach is based on the idea that the maximum profit will be achieved by buying at the lowest price and selling at the highest price after the lowest price.

Initialize variables for the minimum price seen so far (minPrice) and the maximum profit (maxProfit).
Iterate through the prices:
- If the current price is lower than minPrice, update minPrice.
- Otherwise, calculate the potential profit by selling at the current price and update maxProfit if it's higher.
Return the maximum profit.

This method is efficient as it only requires a single pass through the array and has a time complexity of O(n).

Test Cases

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.
Input: prices = [7,6,4,3,1] Output: 0 Explanation: No transaction is done, i.e., max profit = 0.
Input: prices = [2,4,1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

These test cases cover scenarios with profit, no profit, and a short array with profit in the middle.

Rotate Array

Best Time to Buy and Sell Stock II