Best Time to Buy and Sell Stock easy

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.

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 is 0.

Steps

  1. Initialization: We need to track the minimum price encountered so far (minPrice) and the maximum profit (maxProfit). Initialize minPrice to the first price in the array and maxProfit to 0.

  2. Iteration: Iterate through the prices array starting from the second element.

  3. Profit Calculation: For each price, calculate the potential profit by subtracting minPrice from the current price.

  4. Update Maximum Profit: If the calculated profit is greater than maxProfit, update maxProfit.

  5. Update Minimum Price: If the current price is less than minPrice, update minPrice to the current price. This is because we always want to buy at the lowest possible price.

  6. Return Maximum Profit: After iterating through the entire array, return maxProfit.

Explanation

The algorithm uses a single pass through the array to find the maximum profit. It keeps track of the minimum buying price seen so far. For each subsequent price, it calculates the profit that would be obtained by buying at the minimum price and selling at the current price. It updates the maximum profit if a larger profit is found. This approach avoids the need for nested loops, making it efficient.

Code

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices == null || prices.Length < 2) {
            return 0;
        }

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.Length; i++) {
            int potentialProfit = prices[i] - minPrice;
            maxProfit = Math.Max(maxProfit, potentialProfit);
            minPrice = Math.Min(minPrice, prices[i]);
        }

        return maxProfit;
    }
}

Complexity

  • Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once.
  • Space Complexity: O(1). We only use a few constant extra variables.