Compute max profit from single stock trade
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array prices where prices[i] is the stock price on day i, compute the maximum profit achievable with at most one transaction (one buy and one sell, buy before sell). Return 0 if no profit is possible. Aim for O(n) time and O(
1) extra space. Explain the algorithm, prove correctness, and analyze time/space complexity. Optionally, also return the buy and sell indices.
Quick Answer: This question evaluates a candidate's ability to design efficient array algorithms, reason about time and space complexity constraints, and handle edge cases related to single-transaction profit calculation.
Given an array `prices` where `prices[i]` is the price of a given stock on day `i`, find the maximum profit you can achieve from at most one transaction (buy on one day and sell on a later day). You must buy before you sell. If no profit is possible, return `0`.
Aim for 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 no transaction is profitable; return 0.
Constraints
- 0 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4
- You may complete at most one transaction (one buy followed by one later sell).
- If no profitable transaction exists, return 0.
Examples
Input: ([7, 1, 5, 3, 6, 4],)
Expected Output: 5
Explanation: Buy at 1 (day 1), sell at 6 (day 4); profit = 5, the maximum achievable.
Input: ([7, 6, 4, 3, 1],)
Expected Output: 0
Explanation: Prices strictly decrease, so any buy-then-sell loses money; return 0.
Hints
- Track the lowest price seen so far as you scan left to right; the best sell-on-day-i profit is prices[i] minus that running minimum.
- Keep two running values: the minimum price so far and the maximum profit so far. Update profit before lowering the minimum, since you must buy strictly before you sell.
- Brute force tries every (buy, sell) pair in O(n^2); the single-pass approach collapses this to O(n) time and O(1) space.