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'll need a variable to track the minimum price encountered so far (min_price) and a variable to track the maximum profit (max_profit). Initialize both to 0.

2. Iteration: Iterate through the prices array.

3. Minimum Price Update: In each iteration, update min_price if a lower price is found.

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

5. Maximum Profit Update: Update max_profit if the calculated profit is greater than the current max_profit.

Explanation

The algorithm uses a single pass through the array. It keeps track of the minimum buying price encountered so far. For every price, it calculates the potential profit if it were to sell at that price. The maximum of all these potential profits represents the maximum profit achievable. This approach avoids checking every possible buy-sell combination, making it efficient.

Code

def maxProfit(prices):
    """
    Finds the maximum profit from buying and selling a stock once.

    Args:
        prices: A list of integers representing stock prices on different days.

    Returns:
        The maximum profit achievable, or 0 if no profit can be made.
    """
    min_price = float('inf')  # Initialize with positive infinity
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)  # Update minimum price
        profit = price - min_price        # Calculate potential profit
        max_profit = max(max_profit, profit) # Update maximum profit

    return max_profit

Complexity

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