Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

What is this problem about?

The "Best Time to Buy and Sell Stock interview question" is perhaps the most famous coding challenge in the world. You are given an array of prices where prices[i] is the price of a given stock on day $i$. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. If no profit can be made, return 0.

Why is this asked in interviews?

This "Best Time to Buy and Sell Stock coding problem" is asked by literally every major tech company, from Google to Apple to Bloomberg. It is the perfect introductory problem to test "Dynamic Programming" and "Array interview pattern" logic. It assesses if a candidate can optimize a search from $O(N^2)$ to $O(N)$ by keeping track of a "running minimum."

Algorithmic pattern used

The solution uses a Single Pass Greedy approach.

1. Initialize: Set min_price to infinity and max_profit to 0.
2. Iterate: For every price in the array:
   • If the current price is lower than min_price, update min_price.
   • Otherwise, calculate the potential profit if you sold today: current_price - min_price.
   • Update max_profit if the current potential profit is higher. This ensures you always buy at the lowest point seen before the current day.

Example explanation

Prices: [7, 1, 5, 3, 6, 4]

• Day 1 (7): min_price = 7.
• Day 2 (1): min_price = 1.
• Day 3 (5): Profit = $5 - 1 = 4$. max_profit = 4.
• Day 4 (3): Profit = $3 - 1 = 2$.
• Day 5 (6): Profit = $6 - 1 = 5$. max_profit = 5.
• Day 6 (4): Profit = $4 - 1 = 3$. Max Profit: 5.

Common mistakes candidates make

• Selling before buying: Not enforcing the $i < j$ (buy before sell) constraint.
• Nested Loops: Using two loops to check every pair of days, which is $O(N^2)$ and will time out on large datasets.
• Initial Values: Setting min_price to 0 instead of a very large number, which prevents it from ever being updated by the actual prices.

Interview preparation tip

This is the "Hello World" of Dynamic Programming. Master this logic before moving on to its more complex variations (Stock II, III, IV). It teaches you the vital skill of "tracking the state" while moving through an array.