Maximize one stock trade profit
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You're given an array prices of length n where prices[i] is the stock price on day i. You may complete at most one transaction (buy once, then sell later). Return the maximum possible profit; if no profit is possible, return 0.
Constraints: 1 <= n <= 100000, 0 <= prices[i] <= 1e9.
Requirements: O(n) time and O(
1) extra space. Provide the algorithm, prove correctness, and analyze complexity.
Follow-up: adapt your solution to a streaming setting where prices arrive one by one and you must output the current best profit after each new price.
Quick Answer: This question evaluates algorithm design skills for single-pass array processing, streaming data handling, and time/space complexity analysis within the Coding & Algorithms domain.
You're given an array `prices` of length `n` where `prices[i]` is the stock price on day `i`. You may complete at most one transaction: buy on one day and sell on a strictly later day. Return the maximum possible profit. If no profit is possible, return 0.
You must achieve O(n) time and O(1) extra space.
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.
Example 2:
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Prices only fall, so the best choice is to make no transaction; profit = 0.
Approach: scan left to right while tracking the minimum price seen so far. For each day, the best profit if you sell today is `price - min_so_far`; keep the running maximum of that quantity. Each price is the lowest possible buy point for any sell that comes after it, so this single pass finds the global optimum.
Follow-up (streaming): the same two running variables (`min_so_far`, `best`) let you emit the current best profit after each new price arrives, in O(1) per update and O(1) total extra space.
Constraints
- 1 <= n <= 100000
- 0 <= prices[i] <= 1e9
- Required: O(n) time and O(1) extra space
- Buy must occur strictly before the sell day
Examples
Input: [7, 1, 5, 3, 6, 4]
Expected Output: 5
Explanation: Buy at 1 (day 1), sell at 6 (day 4): profit 5.
Input: [7, 6, 4, 3, 1]
Expected Output: 0
Explanation: Strictly decreasing prices; no profitable trade, so 0.
Hints
- You only need the lowest price seen so far to evaluate any potential sale today.
- For each day, the best profit ending today is current_price minus the minimum price before it.
- Track two running values in one pass: the minimum price so far and the maximum profit so far.
- If prices never rise above an earlier value, the answer is 0 (make no trade).