GitHub

Best Time to Buy and Sell Stock easy

Description

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

You want to maximize your profit by choosing a single day to buy and a single day to sell in the future. Return the maximum profit you can achieve. If you can’t achieve any profit, return 0.

Examples

> Case 1:
    Input: prices = [7, 1, 5, 3, 6, 4]
    Output: 5
    Explanation: Buy on day 1 (price = 1) and sell on day 4 (price = 6).
                 Profit = 6 - 1 = 5.
 
> Case 2:
    Input: prices = [7, 6, 4, 3, 1]
    Output: 0
    Explanation: Prices only decrease. No profitable transaction possible.

Constraints

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

Key Insight

We want to find the maximum difference prices[j] - prices[i] where j > i. We track the minimum price seen so far and check if selling at the current price gives a better profit.

Buy & Sell: prices = [7, 1, 5, 3, 6, 4]

Step 1 of 6

7

[0]

1

[1]

5

[2]

3

[3]

6

[4]

4

[5]

Day 0: price=7. minPrice=7, profit=0.

Code

Explanation

We iterate through prices left to right
At each day, we know the cheapest price we could have bought at (everything to the left)
The profit of selling today is prices[i] - minPrice
We keep track of the best profit seen across all days
If prices only decrease, maxProfit stays at 0 (we simply don’t trade)

Connection to Kadane’s: This problem is actually a variant of Kadane’s algorithm. If you compute the daily price changes [−6, 4, −2, 3, −2] and find the max subarray sum, you get 5 — the same answer. The “best buying day” corresponds to the start of the max subarray.

Analysis

Time Complexity: O(n) — single pass through the array
Space Complexity: O(1) — two variables

Kadane's Algorithm Merge Intervals