Best Time to Buy and Sell Stock

Problem in Plain English

Given an array prices where prices[i] is the price of one stock on day i, choose one day to buy and a later day to sell so that the profit is as large as possible. Return that maximum profit, or 0 when no profitable trade exists.

Problem Statement

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

Choose a single day to buy one stock and a different, later day to sell it, maximising prices[sell] - prices[buy]. Return that maximum profit, or 0 when no pair of days yields a profit.

Constraints

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

Examples

Example 1

Input: prices = [7,1,5,3,6,4]
Output: 5

Buying on day 2 (index 1) at price 1 and selling on day 5 (index 4) at price 6 gives profit 6 - 1 = 5. The earlier 7 cannot be a sale after buying at 1.

Example 2

Input: prices = [7,6,4,3,1]
Output: 0

Every later price is lower than every earlier one, so no trade earns money and the answer is 0.

Example 3

Input: prices = [5]
Output: 0

There is no later selling day, so no transaction is possible. Return the no-trade profit 0.

Example 4

Input: prices = [9,1]
Output: 0

The only legal trade loses 8. Subtracting the global minimum from the global maximum would incorrectly give 8, because it would sell before buying.

Example 5

Input: prices = [2,5,1,2]
Output: 3

Buy at 2 and sell at the next 5 for profit 3. The later minimum 1 offers only a later sale at 2, for profit 1; finding a new minimum does not reset the best completed profit.

Intuition

Imagine checking each day as a possible selling day while remembering the cheapest earlier price. For a fixed sale price, paying less earlier can only improve the profit, so other earlier buy prices can be forgotten. In [7, 1, 5, 3, 6, 4], after seeing 1, the sale prices 5, 3, 6, and 4 offer profits 4, 2, 5, and 3. Keep the largest, 5. A new low helps future sales, but must not erase a better completed trade. The initial answer 0 represents choosing no trade.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Every legal trade is a buy day paired with a later sell day, so testing all such pairs and keeping the best profit cannot miss the answer. The cost is checking a quadratic number of pairs.

Step-by-Step Logic

Initialize maxProfit = 0, allowing no trade when all legal pairs lose money.
For each buy index i from 0 through n - 2, inspect every sell index j from i + 1 through n - 1. This enforces a later sale.
Compute profit = prices[j] - prices[i] and replace maxProfit only if this profit is greater. In Example 1, buying at index 0 gives five losses, leaving the best at 0.
Buying at index 1 (price 1) gives profits 4, 2, 5, and 3; the running best rises first to 4, then to 5.
Continue all remaining pairs and return the largest nonnegative profit. Example 1 checks 15 pairs and returns 5; a singleton checks no pairs and returns 0.

Why It Works

Every permitted trade has exactly one buy index i and sell index j with i < j. The nested loops visit every such pair once and never visit an illegal ordering. After each pair, maxProfit is the maximum of zero and all profits considered so far, because it is updated only for a better profit. At termination that set includes all legal trades, so the answer is the optimal profit or zero if every trade is unprofitable. No pair exists for a singleton, leaving the initial zero intact.

Dry Run

Brute Force: variable states at each step
Buy i and price	Sell j and price	Profit	maxProfit before	maxProfit after
Initialize	none	none	none	`0`
`0`, `7`	`1`, `1`	`-6`	`0`	`0`
`0`, `7`	`2`, `5`	`-2`	`0`	`0`
`0`, `7`	`3`, `3`	`-4`	`0`	`0`
`0`, `7`	`4`, `6`	`-1`	`0`	`0`
`0`, `7`	`5`, `4`	`-3`	`0`	`0`
`1`, `1`	`2`, `5`	`4`	`0`	`4`
`1`, `1`	`3`, `3`	`2`	`4`	`4`
`1`, `1`	`4`, `6`	`5`	`4`	`5`
`1`, `1`	`5`, `4`	`3`	`5`	`5`
`2`, `5`	`3`, `3`	`-2`	`5`	`5`
`2`, `5`	`4`, `6`	`1`	`5`	`5`
`2`, `5`	`5`, `4`	`-1`	`5`	`5`
`3`, `3`	`4`, `6`	`3`	`5`	`5`
`3`, `3`	`5`, `4`	`1`	`5`	`5`
`4`, `6`	`5`, `4`	`-2`	`5`	`5`
Finish	none	none	`5`	return `5`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

For n prices, the inner-loop lengths are n-1, n-2, through 1, totaling n(n-1)/2 pair evaluations. Constant work per pair gives O(n^2) time. Loop indices, one profit, and the running best need O(1) extra space, with no input mutation. A singleton takes constant time. At n=100000 this approach evaluates 4,999,950,000 pairs and is impractical.

Code

Solution.java

1class Solution {2    public int maxProfit(int[] prices) {3        int maxProfit = 0;4        for (int i = 0; i < prices.length - 1; i++) {5            for (int j = i + 1; j < prices.length; j++) {6                int profit = prices[j] - prices[i];7                if (profit > maxProfit) {8                    maxProfit = profit;9                }10            }11        }12        return maxProfit;13    }14}

Hints

Hint 1

Selling on day i is best paired with the cheapest price among the days before i, so what single value is worth carrying forward?

Hint 2

One left-to-right scan can keep both that cheapest price and the best profit seen so far.

Hint 3

A price below the current minimum starts a better buy opportunity instead of a sale.

Edge Cases

Steadily falling prices such as [7, 6, 4, 3, 1], where the minimum keeps dropping and the answer stays 0.
A single day such as [5], where no sale is possible and the answer is 0.
Equal prices [4, 4, 4] have legal trades but no gain, so return 0.
Global maximum before minimum: [9, 1] returns 0, not 8; order matters.
A later new low after a profitable trade: [2, 5, 1, 2] returns 3; keep the earlier best profit while updating the buy candidate.
Boundary values [0, 10000] return 10000; [10000, 0] returns 0.
Several opportunities [1, 3, 2, 5] return 4 for one trade; summing separate gains would solve a different multiple-transaction problem.

Common Mistakes and Interview Tips

Allowing the sell day to precede the buy day by taking a global maximum minus a global minimum regardless of order.
Resetting the minimum price on every profitable day instead of only when a strictly lower price appears.
Testing all $O(n^2)$ day pairs, which performs billions of evaluations at n = 10^5.
Initializing the answer to a negative loss forces a trade even when doing nothing should return 0.
Resetting maxProfit when a new minimum appears loses the best completed trade, as [2, 5, 1, 2] demonstrates.
Summing every upward price move permits multiple transactions instead of the required single buy and sell.
Interview tip: explain what each state stores before the current day. The earlier minimum enforces the time ordering without storing every buy candidate.

Key Takeaway

When each position pairs with the best value before it, one forward scan carrying that best-so-far state replaces a quadratic pair search.