AlgoViz
HomeArrays & Hashing

Stock Buy and Sell

Medium

Track the cheapest day so far

Problem

Given an array arr of n integers, where arr[i] represents price of the stock on the ith day. Determine the maximum profit achievable by buying and selling the stock at most once. The stock should be purchased before selling it, and both actions cannot occur on the same day.

In simple words

Track the cheapest price so far and, at each day, see how much you'd earn selling today.

The idea

Sweep left to right keeping the minimum price seen and the best profit if you sold today. Because the minimum is always from an earlier day, the buy-before-sell ordering is enforced automatically.

The trick

  • Update the profit before updating the minimum, so you never buy and sell on the same day.
  • Profit can never be negative — the answer is 0 if prices only fall.
  • O(n), one pass.
7
1
5
3
6
4
0
1
2
3
4
5

Step 1 of 17. Brute force: try buying on every day and selling on every later day. Values: 7, 1, 5, 3, 6, 4.

1/17
Brute force
timeO(n²)spaceO(1)

Every buy/sell pair.

1for (let i = 0; i < n; i++)2  for (let j = i + 1; j < n; j++)3    best = Math.max(best, prices[j] - prices[i]);

Input

array
[7, 1, 5, 3, 6, 4]

Memory

buy
—
sell
—

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
prices = [7, 1, 5, 3, 6, 4]
Output:
5
Explanation:
Buy at 1, sell at 6 → profit 5.

Example 2

Input:
prices = [7, 6, 4, 3, 1]
Output:
0
Explanation:
Prices only fall, so no profit → 0.

Example 3

Input:
prices = [2, 4, 1]
Output:
2
Explanation:
Buy at 2, sell at 4 → profit 2.

Constraints

  • 1 <= n<= 10^5
  • 0 <= arr[i] <= 10^6

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.