Katkat
Back

Find the Best Profit from One Stock Trade

OracleBackend Engineer · Onsite
MediumBackend EngineerOnsiteCoding & Algorithms

Last updated

Tests array traversal, greedy state tracking, and achieving optimal O(n) time and O(1) space complexity for trade optimization.

Problem Statement

You are given an array of integers prices where prices[i] represents the price of a given stock on day i.

You want to maximize your profit by choosing a single day to buy one share of the stock and choosing a different day in the future to sell that share.

Return the maximum profit you can achieve from this trade. If you cannot achieve any profit (for example, if prices continually decrease), return 0.

Function Signature

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

Input & Output Format

  • Input: A list of integers prices representing daily stock prices.
  • Output: An integer representing the maximum profit achievable.

Constraints

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

Examples

Example 1

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 1 (price = 1) and sell on day 4 (price = 6), profit = 6 - 1 = 5.
Note that buying on day 1 and selling on day 0 is not allowed because you must buy before you sell.

Example 2

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Edge Cases to Consider

  • Arrays of length 1: No trade can be completed, result must be 0.
  • Strictly decreasing prices: No trade yields positive profit, result must be 0.
  • Identical prices across all days: Profit remains 0.

Hints

Hint 1

Consider what information you need at each day to decide your maximum profit if you were forced to sell on that day.

Hint 2

As you iterate through the prices, keep track of the lowest price observed up to that point.

Hint 3

Calculate the potential profit at each day using the running minimum and update the global maximum profit.

Follow-up questions

  • How would you adapt your approach if you are allowed to complete at most two transactions?
  • How does the solution change if every transaction incurs a fixed flat transaction fee?
  • If the price data arrives as a continuous infinite stream, how would you design an online algorithm to report the current maximum profit?