Stock Buy and Sell Optimal Solution using Single Pass

Given an array prices, where prices[i] represents the stock price on the ith day, your task is to find the maximum profit you can achieve by choosing a single day to buy one stock and a different day in the future to sell that stock.

• You must buy the stock before you sell it.
• If there is no way to make a profit, return 0.

Understanding the Problem

We are given an array of stock prices, where each element represents the price of a stock on a particular day. Our goal is to find the best day to buy and the best day to sell the stock to maximize profit. However, we are allowed to make this transaction only once, and we must buy the stock before we sell it.

In simple terms, we want to choose two days: one for buying and one for selling. The profit is the difference between the selling price and the buying price. If no profit is possible (i.e., prices only go down), we return 0.

Step-by-Step Solution with Explanation

1. Track the Minimum Price

As we go through the list, we will keep track of the lowest price we’ve seen so far. This will represent the best day to buy so far.

2. Calculate Profit

At each step, we calculate the profit if we were to sell the stock on that day, using the lowest price we've seen before. If this profit is greater than the best profit we’ve recorded, we update our best profit.

3. Use Example for Better Understanding

Let’s understand this with a beginner-friendly example: [7, 1, 5, 3, 6, 4]

• Day 1: Price = 7 → minPrice = 7
• Day 2: Price = 1 → minPrice = 1 (found a cheaper buy)
• Day 3: Price = 5 → profit = 5 - 1 = 4 → maxProfit = 4
• Day 4: Price = 3 → profit = 3 - 1 = 2 → maxProfit remains 4
• Day 5: Price = 6 → profit = 6 - 1 = 5 → maxProfit = 5
• Day 6: Price = 4 → profit = 4 - 1 = 3 → maxProfit remains 5

Result: Best profit is 5 (Buy at 1, sell at 6)

Handling Edge Cases

Case 1: Prices Only Go Down

Example: [7, 6, 4, 3, 1]
The price keeps dropping. Any buy-sell pair results in a loss. So, the maximum profit is 0.

Case 2: Constant or Steady Increase

Example: [1, 2, 3, 4, 5]
Here, buying at day 1 and selling at day 5 gives the best result: profit = 5 - 1 = 4.

Case 3: Single Price

Example: [10]
We can’t sell if we buy on the only day available. So, the profit is 0.

Case 4: Empty Array

There are no prices at all, so no transaction can be made. The answer is 0.

1. Given an array prices where prices[i] represents the price of a stock on the ith day.
2. Initialize min_price to a very large number and max_profit to 0.
3. Traverse through the array:
4. → If prices[i] is less than min_price, update min_price.
5. → Else, calculate the profit by prices[i] - min_price and update max_profit if it is greater.
6. After the loop, return max_profit.

O(1)

Explanation: The solution uses a constant amount of extra space, maintaining only variables like min_price and max_profit.