Katkat
Back

Maximum Profit from One Stock Purchase and a Later Sale

XiaohongshuSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to solve the 'best time to buy and sell stock' pattern in O(n) time and O(1) space, identifying the minimum price seen so far to calculate potential profit.

Problem Statement

You are given an array of integers prices where prices[i] represents the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one share and choosing a different day in the future to sell that share.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Function Signature

def max_profit(prices: list[int]) -> int:

Constraints

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

Examples

Example 1: Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5. Note that buying on day 2 and selling on day 3 yields a profit of 4, which is not the maximum.

Example 2: Input: prices = [7, 6, 4, 3, 1] Output: 0 Explanation: In this case, no transaction is done, as the price never increases.

Edge Cases

  • Array length of 1.
  • Prices strictly decreasing.
  • Prices constant (e.g., [5, 5, 5]).

Hints

Hint 1

A brute-force approach comparing every pair of days would take O(n^2) time; can you keep track of the minimum price encountered as you iterate through the array once?

Hint 2

At any given day `i`, the potential profit if you sell on that day is `prices[i]` minus the minimum price seen before day `i`.

Hint 3

Maintain a variable for the `min_price` seen so far and update a `max_profit` variable whenever the current price minus `min_price` exceeds the current `max_profit`.

Follow-up questions

  • How would your approach change if you were allowed to complete multiple transactions (i.e., buy and sell multiple times, but only hold one share at a time)?
  • What if you were restricted by a 'cooldown' period where you cannot buy a stock the day after you sell it?
  • How would you modify the algorithm to return the indices of the buy and sell days instead of the profit?