Maximize stock profit with one or two trades
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given an array `prices` where `prices[i]` is the price of a given stock on day `i` (0-indexed).
You want to maximize your profit by choosing when to buy and sell this stock, subject to the constraints below. You may not hold more than one share at a time (i.e., you must sell before you can buy again).
Assume:
- `1 <= n <= 10^5`, where `n = prices.length`.
- `0 <= prices[i] <= 10^4`.
### Part A: At most one transaction
You are allowed to complete **at most one** transaction (i.e., buy once and sell once).
- Return the **maximum profit** you can achieve.
- If no profit is possible, return `0`.
**Example**
- 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.
---
### Part B: At most two transactions
Now you are allowed to complete **at most two transactions**.
- Each transaction is a buy followed by a sell.
- You must sell the stock before you buy again.
- You cannot engage in multiple transactions at the same time.
Return the **maximum total profit** you can achieve with at most two transactions.
**Example**
- Input: `prices = [3, 3, 5, 0, 0, 3, 1, 4]`
- Output: `6`
- Explanation:
- Buy on day 3 (price = 0), sell on day 5 (price = 3), profit = 3.
- Then buy on day 6 (price = 1), sell on day 7 (price = 4), profit = 3.
- Total profit = 3 + 3 = 6.
Design algorithms for both parts that run in **O(n)** time and **O(1)** or **O(n)** extra space.
Quick Answer: This question evaluates algorithmic problem-solving skills in array processing and transaction-constrained optimization, exercising greedy and dynamic programming concepts within the Coding & Algorithms domain.
Maximize Stock Profit — Part A: At Most One Transaction
You are given an array `prices` where `prices[i]` is the price of a given stock on day `i` (0-indexed).
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. You are allowed to complete **at most one** transaction (buy once and sell once).
Return the **maximum profit** you can achieve from this transaction. If you cannot achieve any profit, return `0`.
**Example**
- 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.
**Approach:** Track the minimum price seen so far while scanning left to right; at each day the best profit ending today is `price − min_so_far`. Keep the maximum over all days.
Constraints
- 1 <= n <= 10^5, where n = prices.length
- 0 <= prices[i] <= 10^4
- You must buy before you sell (sell day strictly after buy day)
- At most one transaction
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: Prices only fall; no profitable trade, return 0.
Input: ([1],)
Expected Output: 0
Explanation: Single day, cannot buy and sell on different days, return 0.
Input: ([1, 2, 3, 4, 5],)
Expected Output: 4
Explanation: Buy at 1, sell at 5: profit 4.
Input: ([2, 4, 1],)
Expected Output: 2
Explanation: Buy at 2 (day 0), sell at 4 (day 1): profit 2; the later 1 is too late and too low.
Input: ([3, 3, 3],)
Expected Output: 0
Explanation: Flat prices yield no profit, return 0.
Hints
- You only ever care about the lowest price you've seen so far when deciding where to sell today.
- Scan once, maintaining the running minimum price and the best profit (current price minus running minimum).
- If prices only decrease, no profitable transaction exists, so the answer is 0.
Maximize Stock Profit — Part B: At Most Two Transactions
You are given an array `prices` where `prices[i]` is the price of a given stock on day `i` (0-indexed).
You are now allowed to complete **at most two transactions**. Each transaction is a buy followed by a sell. You must sell the stock before you can buy again (you may not hold more than one share at a time).
Return the **maximum total profit** you can achieve with at most two transactions.
**Example**
- Input: `prices = [3, 3, 5, 0, 0, 3, 1, 4]`
- Output: `6`
- Explanation: Buy on day 3 (price = 0), sell on day 5 (price = 3) for profit 3; then buy on day 6 (price = 1), sell on day 7 (price = 4) for profit 3. Total = 6.
**Approach:** Track four running values as you scan: `buy1` (lowest effective cost of the first buy), `profit1` (best profit after one sell), `buy2` (lowest effective cost of the second buy, net of profit1), and `profit2` (best total profit after the second sell). Each is updated in O(1) per day, giving O(n) time and O(1) space.
Constraints
- 1 <= n <= 10^5, where n = prices.length
- 0 <= prices[i] <= 10^4
- You must sell before buying again (no overlapping transactions)
- At most two transactions
Examples
Input: ([3, 3, 5, 0, 0, 3, 1, 4],)
Expected Output: 6
Explanation: Buy 0 sell 3 (profit 3), buy 1 sell 4 (profit 3): total 6.
Input: ([1, 2, 3, 4, 5],)
Expected Output: 4
Explanation: A single rising run is captured by one transaction (buy 1, sell 5): profit 4; a second transaction adds nothing.
Input: ([7, 6, 4, 3, 1],)
Expected Output: 0
Explanation: Prices only fall; no profitable trades, return 0.
Input: ([1],)
Expected Output: 0
Explanation: Single day, no transaction possible, return 0.
Input: ([1, 2, 4, 2, 5, 7, 2, 4, 9, 0],)
Expected Output: 13
Explanation: Buy 1 sell 7 (profit 6), buy 2 sell 9 (profit 7): total 13.
Input: ([3, 3, 3],)
Expected Output: 0
Explanation: Flat prices yield no profit, return 0.
Hints
- You can extend the one-transaction state machine: track the best state after buy 1, sell 1, buy 2, and sell 2.
- For the second buy, treat its effective cost as the current price minus the profit already locked in from the first transaction.
- Update all four states in a single left-to-right pass; the answer is the best profit after the second sell.
- If only one transaction is profitable, the second-transaction states naturally collapse so the answer still reflects at most two trades.