Best Time to Buy and Sell Stock

Problem Statement

Given an integer array prices, where prices[i] represents the stock price on the i-th day, return the maximum profit that can be earned by buying the stock on one day and selling it on a later day.

Return 0 when no profitable transaction is possible.

Brute Force Approach

The most direct idea is to try every day as a buying day and pair it with every possible selling day that comes later.

Each pair represents one valid transaction. Calculating the profit for every pair guarantees the correct answer, but many prices are compared repeatedly.

Algorithm

• Store the number of days in n. Return 0 when fewer than two prices are available because buying and selling require two different days.

• Initialize maxProfit with 0. This value represents choosing no transaction when every possible buy-and-sell pair produces a loss.

• Use buy to select every possible buying day from index 0 through n - 2. The final day is excluded because no later selling day would remain.

• For each buy, move sell from buy + 1 through n - 1. Starting after buy guarantees that the stock is always sold after being purchased.

• Calculate the profit for the current pair as prices[sell] - prices[buy] and update maxProfit whenever the current transaction produces a larger profit.

• Return maxProfit after every valid transaction has been examined.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N²), where N represents the number of days. Every buying day is paired with every possible later selling day.

Space Complexity: O(1), because only the loop indices, currentProfit, and maxProfit require auxiliary storage.

Optimal Approach

For any selling day, the best profit must come from buying at the lowest price seen before that day.

Therefore, the complete history of earlier prices is unnecessary. Only the cheapest earlier price needs to be remembered. Each current price can then be treated as a possible selling price and compared against that cheapest buying opportunity.

Algorithm

• Store the number of days in n. Return 0 when n is smaller than 2 because a valid transaction requires separate buying and selling days.

• Initialize minPrice with prices[0]. This variable stores the cheapest buying price found before the current selling day.

• Initialize maxProfit with 0, representing the choice to skip the transaction when all later prices are lower.

• Traverse the prices from index 1. Treat the current price as a possible selling price and calculate currentProfit = prices[index] - minPrice.

• Update maxProfit when the current selling opportunity produces a larger profit. Then update minPrice when the current price is cheaper, allowing the current day to become a buying candidate for future days.

• Return maxProfit after every possible selling day has been evaluated.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the number of days. Every stock price is processed exactly once.

Space Complexity: O(1), because only minPrice, currentProfit, and maxProfit require auxiliary storage.

FAQs

Q1. Why must minPrice represent a price from an earlier day?

A valid transaction requires buying before selling. When the current price is evaluated as a selling price, minPrice must therefore come from an already processed day.

Q2. Why is the profit calculated before updating minPrice?

Calculating the profit first keeps the current day in the selling role and uses only an earlier day for buying. Afterward, the current price may become a buying candidate for future selling days.

Q3. How can the Optimal Approach return the buying and selling days?

Store the index whenever minPrice changes. When maxProfit improves, save that minimum-price index as the buying day and the current index as the selling day.

Q4. What changes when exactly one transaction must be completed, even at a loss?

Initializing maxProfit with 0 would no longer be valid. The answer must instead begin with the profit from the first valid pair, and the algorithm must return the smallest possible loss when no profitable transaction exists.

Q5. How does the solution change when multiple transactions are allowed?

Every positive increase between consecutive days can contribute to the total profit. That variation adds all positive differences instead of selecting only one buy-and-sell pair.