Katkat
Back

Maximize Profit with One Stock Transaction

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to find the optimal buy and sell points for a stock within a single transaction, focusing on an efficient O(n) single-pass approach.

Problem Statement

You are given an array of integers prices where prices[i] is 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 stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If no profit can be made (i.e., the price never increases), 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 1 is not allowed.

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

Edge Cases to Consider

  • Empty list or a list with a single element.
  • Prices strictly decreasing.
  • Prices strictly increasing.
  • Identical prices throughout the array.

Hints

Hint 1

Instead of looking at all possible pairs of buy and sell days, can you keep track of the minimum price encountered so far while iterating?

Hint 2

At each day `i`, the potential profit you could make is `prices[i] - min_price_so_far`.

Hint 3

Update your global maximum profit whenever you find a new peak difference during your single pass through the array.

Follow-up questions

  • How would your approach change if you were allowed to complete multiple transactions (i.e., buy and sell multiple times)?
  • What is the time and space complexity of your solution, and can you explain why it is optimal?
  • How would you modify the function to return the indices of the buy and sell days instead of the profit?