Best Time to Buy and Sell Stock

easyFREESliding WindowBlind 75

Given an array prices where prices[i] is the price of a given stock on the i-th day, find the maximum profit you can achieve by buying on one day and selling on a later day.

If no profit is possible, return 0.

Example

Input

7,1,5,3,6,4

Output

Reasoning

The input prices lists one price per day: day 1 is $7$ , day 2 is $1$ , then $5, 3, 6, 4$ on days 3 to 6.
A trade is a pair of days $i < j$ : buy at $p_i$ , sell at $p_j$ , profit $p_j - p_i$ . The output is the largest such profit, or $0$ if every pair loses money.
Buying on day 1 at $7$ never pays: every later price is lower, so all those profits are negative.
Buying on day 2 at $1$ is far better. Selling on days 3, 4, 5, 6 gives $5-1=4$ , $3-1=2$ , $6-1=5$ , $4-1=3$ . The best is $5$ (sell on day 5 at $6$ ).
Every other buy day starts higher than $1$ (buy at $3$ and sell at $6$ gives only $3$ ), so the answer is 5.
Notice that $7 - 1 = 6$ is not allowed: the $7$ comes before the $1$ , and you cannot sell before you buy. If prices only ever fall, no pair profits, so the answer is 0.

Constraints

1 <= len(prices) <= 10^5
0 <= prices[i] <= 10^4

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The "Best Time to Buy and Sell Stock" problem is a classic example of a sliding window problem, although it can also be approached with a single pass through the data, keeping track of the minimum price seen so far and the maximum profit that can be achieved. The key concept here is to understand that we are looking for a subarray (or a window) within the given array of prices where the difference between the maximum and minimum values represents the maximum possible profit. This problem involves understanding how to efficiently scan through the array to find this optimal window.

In the context of dynamic programming and greedy algorithms, this problem can be solved by maintaining a running minimum of the stock prices seen so far and calculating the potential profit at each step. The idea is to buy at the lowest price and sell at the highest price, but since we can only sell after we buy, we need to ensure that our selling price is indeed after our buying price in the timeline. This problem does not require the use of a traditional sliding window of fixed size but rather a conceptual window that represents the period between buying and selling.

The mathematical concept behind this problem involves finding the maximum value of the difference between two elements in an array, with the constraint that the element representing the selling price must come after the element representing the buying price. This can be expressed as finding the maximum value of $prices[j] - prices[i]$ where $j > i$ . The goal is to maximize this difference, which represents the profit.

Algorithm/Approach

The general approach to solving this type of problem involves iterating through the array of prices and at each step, considering whether the current price could be a potential buying or selling point that maximizes profit. This can be achieved through a greedy algorithm that keeps track of the minimum price seen so far and the maximum profit that can be achieved up to the current point.

Step-by-Step Strategy

Initialize variables to keep track of the minimum price seen so far and the maximum profit achievable.
Iterate through the array of prices. For each price:

Update the minimum price if the current price is lower.
Calculate the potential profit if we were to sell at the current price after buying at the minimum price seen so far.
Update the maximum profit if the calculated potential profit is higher.

After iterating through all prices, the maximum profit variable will hold the maximum achievable profit.

Common Pitfalls

Forgetting to update the minimum price when encountering a lower price.
Incorrectly calculating the potential profit by not considering the constraint that selling must occur after buying.
Not initializing variables properly before starting the iteration.

Time & Space Complexity

Time Complexity: $O(n)$ , where $n$ is the number of days (i.e., the length of the prices array), because we are making a single pass through the array.
Space Complexity: $O(1)$ , because we are using a constant amount of space to store the minimum price and the maximum profit, regardless of the size of the input array.

solution.py

Python 3.13

Test results