LeetCode #1423 Medium

Maximum Points You Can Obtain from Cards

Take exactly k cards, one at a time, from either end of the row. Return the maximum score obtainable.

sliding-windowarrayprefix-sum

02

Intuition

💡

There are 2^k orders in which to take cards, but only k + 1 distinct outcomes: whatever you do, you end up with some prefix of length i and some suffix of length k - i. Order does not affect the total. So start with all k cards taken from the left, then repeatedly hand one back from the right end of that prefix and take one more from the far right instead — k + 1 splits, each an O(1) update.

03

Approach

1

Collapse the choice order

Taking left-then-right and right-then-left yield the same two cards and the same score. What matters is only how many came from each end. Since exactly k are taken, the outcome is fully described by one number i: the count taken from the left, with k - i from the right. That reduces 2^k orderings to k + 1 cases.

2

Slide between the splits in O(1)

Compute the sum of the first k cards — the i = k case. To move to i = k - 1, subtract the last card of the prefix and add the last card of the array. Each subsequent split is another subtract-and-add. Track the running maximum across all k + 1 splits. Total work: one O(k) setup and O(k) updates.

3

The complementary framing

An equivalent and sometimes cleaner view: since you take k cards from the ends, the cards you leave behind form a contiguous window of length n - k in the middle. Maximising what you take is minimising that window's sum, which is a fixed-size sliding-window minimum. Both are O(n); the prefix/suffix version avoids computing the total and reads more directly from the problem statement.

04

Solution & live demo

python

▶1class Solution:
▶2    def maxScore(self, cardPoints, k):
▶3        n = len(cardPoints)
▶4        total = sum(cardPoints[:k])
▶5        best = total
▶6        for i in range(1, k + 1):
▶7            total += cardPoints[n - i] - cardPoints[k - i]
▶8            best = max(best, total)
▶9        return best

05

Edge cases

k == len(cardPoints)

All cards are taken, so the answer is the total. The loop still runs and every split gives the same sum.

k == 1

Only two splits exist — the first card or the last — and the maximum of the two is returned.

Negative values

LeetCode constrains points to be positive, but the algorithm needs no change if they were not: it compares totals, never assuming any card is worth taking.

All values equal

Every split gives the same total, which is returned.

06

Complexity

Time

O(k)

Space

O(1)

One initial sum plus k constant-time updates. Enumerating every take order would be O(2^k).