Maximize profit with bounded sell window
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an array prices[0..n-1] of daily stock prices and an integer D ≥ 1, you may perform at most one transaction (buy then sell). The sell day j must satisfy i < j ≤ min(i + D, n −
1) for the chosen buy day i. Return the maximum profit and the pair (i, j) achieving it; if no positive profit exists, return 0 and indicate that no transaction should be made. Design an O(n) time, O(
1) extra space algorithm, and discuss how you would adapt it for streaming input and for very large D.
Quick Answer: This question evaluates proficiency in array algorithms, time and space complexity analysis, and techniques for bounded-range optimization and streaming adaptation.
Given an array `prices[0..n-1]` of daily stock prices and an integer `D >= 1`, you may perform **at most one transaction** (buy on some day `i`, then sell on a later day `j`). The sell day must lie within `D` days of the buy day: `i < j <= min(i + D, n - 1)`.
Return the maximum achievable profit together with the buy/sell day pair `(i, j)` that achieves it, as a list `[profit, i, j]`. If no transaction yields a **strictly positive** profit, return `[0, -1, -1]` to indicate that no transaction should be made.
Design an algorithm that runs in **O(n) time and O(1) extra space** (aside from the bounded sliding-window structure, which holds at most `D + 1` indices).
**Examples**
- `prices = [3, 2, 6, 5, 0, 3]`, `D = 2` -> `[4, 1, 2]` (buy at index 1 for 2, sell at index 2 for 6).
- `prices = [7, 6, 4, 3, 1]`, `D = 3` -> `[0, -1, -1]` (prices only fall; no positive profit).
- `prices = [1, 2, 100]`, `D = 1` -> `[98, 1, 2]` (the window forbids buying at index 0 to sell at index 2).
When several `(i, j)` pairs tie on profit, any optimal pair is accepted (the deque approach naturally returns the latest equal-or-cheaper buy index inside the window).
Constraints
- 1 <= D (the sell day j must satisfy i < j <= min(i + D, n - 1)).
- 0 <= n; n may be 0 or 1, in which case no transaction is possible -> [0, -1, -1].
- Prices may be zero or negative (e.g. spread/relative values); profit is prices[j] - prices[i].
- At most one transaction (one buy followed by one later sell).
- Only strictly positive profit counts; ties on profit may return any optimal (i, j).
Examples
Input: ([3, 2, 6, 5, 0, 3], 2)
Expected Output: [4, 1, 2]
Explanation: Buy at index 1 (price 2), sell at index 2 (price 6) within the 2-day window; profit 4.
Input: ([7, 6, 4, 3, 1], 3)
Expected Output: [0, -1, -1]
Explanation: Prices are strictly decreasing, so no buy/sell pair gives positive profit -> no transaction.
Hints
- Fix the sell day j and ask: what is the cheapest buy day i allowed? It must lie in the sliding window [max(0, j - D), j - 1]. So this is a sliding-window-minimum problem, not the classic O(n) running-min trick (which would let you buy arbitrarily far in the past).
- Maintain a monotonic deque of indices whose prices are increasing. The front is always the index of the minimum price in the current window. Before scoring day j, pop front indices that have fallen out of [j - D, j - 1].
- Order matters: evaluate selling at j against the deque front FIRST (the front holds buy days strictly before j), THEN push j itself as a candidate buy day for the next D sell days. For streaming input, you only ever keep the last D prices' worth of deque entries, and for very large D the deque simply stops being a binding constraint (it degenerates to the standard track-the-running-minimum solution).