Problem overview
The method maxProfit receives prices, where prices[i] is the price of a stock on day i, and an integer k. You may complete at most k transactions, a transaction being one buy followed by one sell. You can't hold two shares at once, so each sale must happen before the next purchase. The method returns the largest total profit.
For prices = [3, 2, 6, 5, 0, 3] and k = 2, the answer is 7. Buy at 2 and sell at 6 for a profit of 4, then buy at 0 and sell at 3 for a profit of 3. With prices = [2, 4, 1] and k = 2, only one trade pays off (buy at 2, sell at 4), so the answer is 2.
Approach: find the trades, then pick the k best
The usual solution to this problem is dynamic programming over days and trades, which costs O(n * k). This lesson uses a different idea that doesn't depend on k until the very end, and it also relates to the single-trade and unlimited-trade versions of the problem.
The chart is a series of dips and rises. Every optimal trade buys at the bottom of a dip and sells at the top of the following rise, so the first job is to extract those [bottom, top] price pairs.
The pairs are not yet independent trades, though. Take [1, 4, 2, 7]. The pairs are [1, 4] and [2, 7]. With two trades you take both, for 3 + 5 = 8. With a single trade, the best choice is buy at 1 and sell at 7, for 6, which merges the two pairs into one. The merged trade earns 6, and the profit given up by merging, 4 - 2 = 2, is the extra amount a second trade can add back: 6 + 2 = 8.
The stack-based pass turns the list of pairs into a list of candidate profits that behave as independent trades. Merging two overlapping intervals (b1, t1) and (b2, t2) into (b1, t2) always comes with a second candidate, t1 - b2, so that taking both candidates equals the two separate trades. Once the candidates are independent, the best answer for k trades is simply the sum of the k largest candidates.
Step by step
The lesson builds two helpers first and then maxProfit itself.
- Extract the bottoms and tops in
findBottomTopPrices. Declarenandi, an emptybottomTopPrices, and an outer loop that runs whilei < n. - Slide
bottomdown the dip. It starts atiand moves right while the price is not lower than the next one. Checkbottom + 1 < nfirst, so the comparison never reads past the end. - Slide
topup the rise. It starts atbottomand moves right while the price is not higher than the next one, with the same bounds check first. - Store the pair and move on. Push
[prices[bottom], prices[top]], seti = top + 1, and return the list after the loop. - Turn the pairs into candidate profits in
computeProfits. Keep astackof intervals still open to merging and aprofitsarray. - Loop over the pairs with
for...of, destructuring each intobottomandtop. They are declared withlet, sincebottomcan change during a merge. - Settle intervals that can't grow. While the stack is non-empty and the new bottom is lower than the stacked interval's bottom, the stacked interval can never be extended further. Record its profit and pop it.
- Merge intervals the new one covers. While the stack is non-empty and
topis at least the stacked top, recordstackedTop - bottomas an extra candidate, take over the stacked interval's lower bottom, and pop it. - Push
[bottom, top]so later intervals can still merge with it. - Drain the stack. After the loop, every remaining interval contributes its own profit.
- Finish in
maxProfit. Call the two helpers throughthis, capkat the number of candidates withMath.min, sort the profits in decreasing order and add the firstk.
The solution in TypeScript
class Solution {
computeProfits(bottomTopPrices: number[][]): number[] {
let stack: number[][] = [];
let profits: number[] = [];
for (let [bottom, top] of bottomTopPrices) {
while (stack.length && bottom < stack[stack.length - 1][0]) {
profits.push(stack[stack.length - 1][1] - stack[stack.length - 1][0]);
stack.pop();
}
while (stack.length && top >= stack[stack.length - 1][1]) {
profits.push(stack[stack.length - 1][1] - bottom);
bottom = stack[stack.length - 1][0];
stack.pop();
}
stack.push([bottom, top]);
}
while (stack.length) {
profits.push(stack[stack.length - 1][1] - stack[stack.length - 1][0]);
stack.pop();
}
return profits;
}
findBottomTopPrices(prices: number[]): number[][] {
let n = prices.length, i = 0;
let bottomTopPrices: number[][] = [];
while (i < n) {
let bottom = i;
while (bottom + 1 < n && prices[bottom] >= prices[bottom + 1]) {
++bottom;
}
let top = bottom;
while (top + 1 < n && prices[top] <= prices[top + 1]) {
++top;
}
bottomTopPrices.push([prices[bottom], prices[top]]);
i = top + 1;
}
return bottomTopPrices;
}
maxProfit(prices: number[], k: number): number {
let bottomTopPrices = this.findBottomTopPrices(prices);
let profits = this.computeProfits(bottomTopPrices);
k = Math.min(k, profits.length);
profits.sort((first, second) => second - first);
let result = 0;
for (let i = 0; i < k; ++i) {
result += profits[i];
}
return result;
}
}
Here is what the helpers return on the two examples:
prices [2,4,1], k = 2
findBottomTopPrices -> [[2,4],[1,1]]
computeProfits -> [2,0]
maxProfit -> 2
prices [3,2,6,5,0,3], k = 2
findBottomTopPrices -> [[2,6],[0,3]]
computeProfits -> [4,3]
maxProfit -> 7
TypeScript details worth a look:
- Nested array types.
number[][]is an array of number arrays. Writinglet stack: number[][] = [];matters: without the annotation, an empty array literal may be inferred asany[]and the compiler would not check what you push. - Destructuring in
for...of.for (let [bottom, top] of bottomTopPrices)unpacks each two-element array into two variables. Because they are declared withlet, the assignmentbottom = ...is allowed. - Truthy
stack.length. A length of 0 is falsy, sostack.length && ...stops when the stack is empty. Because&&short-circuits, the check is also what keepsstack[stack.length - 1]from being read on an empty array, where it would giveundefinedand then fail on[0]. - Sorting needs a comparator. With no comparator,
sort()compares elements as strings, so[10, 9, 1].sort()gives[1, 10, 9]. The comparatorsecond - firstsorts numbers in decreasing order. thisin methods. The helpers are methods of the class, so they are called asthis.findBottomTopPrices(prices).- Reassigning a parameter.
k = Math.min(k, profits.length)changes only the local variablek, not the caller's value.
Complexity
Let n be the number of days.
Time: O(n log n). Extracting the pairs is one pass, since i only moves forward. Each pair is pushed onto the stack once and popped at most once, so computeProfits is linear. The sort of the candidates costs O(n log n) and dominates. A selection algorithm that finds the k largest values would bring the total down to O(n).
Space: O(n). The pairs, the stack and the profits each hold at most one entry per dip-and-rise.
Edge cases and common mistakes
- No prices. An empty array gives no pairs and no profits, so the result is 0.
- Prices that only fall.
[5, 4, 3]produces the single pair[3, 3]with profit 0, and the answer is 0. Taking zero-profit candidates never hurts. - Prices that only rise.
[1, 2, 3, 4, 5]is a single pair[1, 5], so the answer is 4 for anykfrom 1 up. klarger than the number of candidates. This is whatMath.minis for. Without it, the loop would addundefinedfrom outside the array, and the sum would becomeNaN.- Merging when only one trade is allowed. For
[1, 4, 2, 7]andk = 1the answer is 6 (buy at 1, sell at 7), not 5, which is the best single pair. Withk = 2it is 8. - Using
>instead of>=in the bottom scan. Equal prices in a row would stop the slide too early, leaving a bottom that is not the end of the dip. - Forgetting the comparator. The profits are small integers here, so a default sort can look right on small tests and still go wrong once a profit of 10 or more meets a smaller one.
Testing
[2, 4, 1]withk = 2gives2.[3, 2, 6, 5, 0, 3]withk = 2gives7, and withk = 1gives4.[1, 4, 2, 7]withk = 1gives6, and withk = 2gives8.[5, 4, 3]withk = 2gives0.[1, 5, 2, 6, 3, 7]withk = 2gives9.