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 keep track of the minimum price encountered so far (minPrice) and the maximum profit (maxProfit). Initialize both to 0.

  2. Iteration: Iterate through the prices array.

  3. Minimum Price Update: For each price, update minPrice if the current price is lower than the current minPrice.

  4. Profit Calculation: For each price, calculate the potential profit by subtracting minPrice from the current price. Update maxProfit if this potential profit is greater than the current maxProfit.

  5. Return: After iterating through all prices, return maxProfit.

Explanation

The algorithm uses a single pass through the array to find the maximum profit. It efficiently keeps track of the minimum buying price encountered so far. At each step, it checks if selling at the current price would yield a higher profit than the maximum profit found so far. This avoids the need for nested loops, which would lead to a less efficient O(n^2) solution.

Code

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE; // Initialize minPrice to a very large value
        int maxProfit = 0;

        for (int price : prices) {
            // Update minPrice if a lower price is found
            minPrice = Math.min(minPrice, price);

            // Update maxProfit if a higher profit is possible
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
}

Complexity

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