Coding · Sliding window
Maximum Points You Can Obtain from Cards
- Reported in several places
- Medium
- SDE
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
A row of cards each shows a number of points. In exactly k moves you take one card per move, always from the left end or the right end of what remains, and your score is the sum of the cards you took. For example, cards [1,2,3,4,5,6,1] with k = 3 give 12, by taking the three cards at the right end: 1, 6 and 5. The row can hold up to 100,000 cards and 1 <= k <= number of cards.
Restated in our own words, not a quote from Flipkart or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: do I have to take exactly k cards, and may I choose left or right freely on every move? Can card values be zero or negative, or are they all positive? Can k equal the number of cards? How long can the row be, and could the total outgrow a normal number?
I will assume k is at least 1 and at most n, values are integers, the total fits in a JavaScript number, and I return only the best total, not which cards were taken. If k equals n, every card is taken and the answer is the whole sum.
Brute force
Say the obvious answer and why it is too slow.
The obvious plan is to try every way to split the k moves: take i cards from the left end and k - i from the right end, for i from 0 to k. Add those cards up from scratch for each split and keep the largest total.
Each split costs O(k) to add up, and there are k + 1 splits, so the whole thing is O(k²). With n and k near 100,000 that is about ten billion additions, far too slow. A recursive "left or right" choice on every move is worse still, 2k paths. Running sums can bring the split loop down to O(k), but the juggling of two ends is easy to get wrong, so I prefer a cleaner view.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(k²)
- Time
- O(n)
- Space
- O(1) extra
Flip the question. Whatever I take, the cards I do not take form one unbroken block in the middle of the row, and that block always has length n - k. The total of all cards is fixed, so score = total - (sum of the block I leave behind). Maximizing the score is the same as minimizing the sum of a window of exactly n - k consecutive cards.
Why is this exactly equivalent? If I take i cards from the left and k - i from the right, the block left behind starts at index i and has length n - k. As i runs from 0 to k, the block start runs over every possible window start, and every window start from 0 to k is reachable by one choice of i. So the set of "left behind" blocks equals the set of all windows of length n - k, nothing more and nothing less.
Now this is a fixed-size sliding window. Build the first window of n - k cards, then slide it one step at a time: add the new card on the right, drop the old card on the left, and keep the smallest sum seen. Each slide is O(1), so the scan is O(n).
Out loud I would say: "Instead of choosing what to take, I choose what to leave, and what I leave is always a contiguous middle stretch of known length."
Walk it through
A dry run on the example, step by step.
| step | window | sum | smallest so far | note |
|---|---|---|---|---|
| build | [1,2,3,4] | 10 | 10 | first window |
| slide 1 | [2,3,4,5] | 14 | 10 | drop 1, add 5 |
| slide 2 | [3,4,5,6] | 18 | 10 | drop 2, add 6 |
| slide 3 | [4,5,6,1] | 16 | 10 | drop 3, add 1 |
| answer | - | - | 10 | 22 - 10 = 12 |
Take cards [1,2,3,4,5,6,1] with k = 3. The total is 22 and the window length is n - k = 4.
The first window [1,2,3,4] sums to 10. Slide right: drop 1 and add 5, giving 14. Slide again: drop 2, add 6, giving 18. Slide a last time: drop 3, add 1, giving 16. The smallest window sum is 10, so the best score is 22 - 10 = 12.
The trace table shows each window, its sum and the smallest sum so far. The smallest block, [1,2,3,4], is what I leave behind, so I took the three cards after it: 5, 6 and 1, which add up to 12 as in the prompt.
The code
Runnable JavaScript, checked against test cases.
function maxScore(cardPoints, k) {
const n = cardPoints.length;
let total = 0;
for (const points of cardPoints) total += points;
const windowSize = n - k;
if (windowSize <= 0) return total;
let windowSum = 0;
for (let i = 0; i < windowSize; i++) windowSum += cardPoints[i];
let smallest = windowSum;
for (let right = windowSize; right < n; right++) {
windowSum += cardPoints[right] - cardPoints[right - windowSize];
if (windowSum < smallest) smallest = windowSum;
}
return total - smallest;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
If k equals n, the window length is 0 and there is nothing to leave behind, so the code returns the total straight away before building any window. If k is 1, the window has n - 1 cards and the answer is the larger of the two end cards, which the same loop finds without a special case. A single card with k = 1 returns that card.
Zeros are harmless: they add nothing to any window sum. Negative values would also work, because the argument is about sums only. The smallest sum starts as the first window's sum, not as zero, so a window of all positive numbers is never beaten by a fake zero. Large rows stay at O(n) time with two running numbers, so there is nothing extra to allocate.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it with a prefix sum from the left and a suffix sum from the right, growing the left count from 0 to k, and why is that also O(k)?
- Does the complement argument still hold when some cards are negative?
- How would you return which cards were taken, not only the total?
- What changes if you must take at least one card from each end?
Where candidates slip
The mistakes this problem punishes.
The classic wrong answer is greedy: on each move take the bigger of the two end cards. It fails because a small card at an end can hide a huge card right behind it, and the greedy never looks past the end.
Other slips: sliding a window of size k and taking the maximum, which answers a different question; getting the window length wrong by one (it is n - k, not n - k + 1); not noticing that k equal to n leaves an empty window (the code here returns the total early); seeding the smallest sum with 0 instead of the first window's sum; and mixing up the added and dropped indices when sliding.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.