Maximum Points You Can Obtain from Cards — LC 1423 Sliding Window Inversion

Problem Statement#

You take exactly k cards, one at a time, from either end of a row. Return the maximum sum of the cards you take.

Constraints:

• 1 less than or equal to cardPoints.length less than or equal to 10 to the 5
• 1 less than or equal to cardPoints[i] less than or equal to 10 to the 4
• 1 less than or equal to k less than or equal to cardPoints.length

Input:  cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
Output: 12

Input:  cardPoints = [2, 2, 2], k = 2
Output: 4

Why This Problem Matters#

LeetCode 1423 — Maximum Points You Can Obtain from Cards is a Google, Amazon, and Meta favorite because it tests an inversion of intuition. The brute-force "try every prefix and suffix combination" runs in O(k), which is fast, but the elegant solution flips the problem entirely: if you take k cards from the ends, the remaining n - k cards form a contiguous window in the middle. Maximizing the picked sum is equivalent to minimizing the contiguous middle window of size n - k.

This reframe is the kind of insight that separates senior candidates from juniors. Interviewers at Google use it to evaluate problem reformulation skill, and Meta uses it as part of a 30-minute pair to gauge how quickly a candidate spots invariants.

In production code, this pattern shows up whenever you allocate from both ends of a buffer or pick from both ends of a sorted leaderboard — common in game scoring, ad bidding, and resource scheduling.

The Core Insight#

The brute force attempts every split of taking i from the left and k - i from the right. That works in O(k), which is acceptable here, but the cleaner solution is the inversion:

• Total sum of the array is fixed.
• The cards you do not take form a contiguous window of size n - k somewhere in the middle.
• Therefore: maximum picked sum equals total sum minus minimum middle window sum.

When k == n, the middle window has size zero, so the answer is the total sum directly. Otherwise, slide a fixed-size window of length n - k, track its minimum sum, and subtract from total.

This trick generalizes: any "pick from ends" question with a fixed pick count is a fixed-size minimum-window problem on the complement.

Visual Dry Run#

Input: cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3. Total = 22, window size = 4.

Answer: 22 minus 10 equals 12.

Solution (Optimal)#

class Solution:
    def maxScore(self, cardPoints, k):
        n = len(cardPoints)
        total = sum(cardPoints)
        if k == n:
            return total
        window_size = n - k
        current = sum(cardPoints[:window_size])
        min_window = current
        for i in range(window_size, n):
            current += cardPoints[i] - cardPoints[i - window_size]
            if current < min_window:
                min_window = current
        return total - min_window

var maxScore = function(cardPoints, k) {
    const n = cardPoints.length;
    let total = 0;
    for (const v of cardPoints) total += v;
    if (k === n) return total;
    const windowSize = n - k;
    let current = 0;
    for (let i = 0; i < windowSize; i++) current += cardPoints[i];
    let minWindow = current;
    for (let i = windowSize; i < n; i++) {
        current += cardPoints[i] - cardPoints[i - windowSize];
        if (current < minWindow) minWindow = current;
    }
    return total - minWindow;
};

Time: O(n) — one pass to total, one pass to slide. Space: O(1) — running sums only.

Common Mistakes#

• Forgetting the k == n short-circuit, which leads to a window of size zero.
• Sliding a window of size k instead of n - k and trying to maximize directly without the complement insight.
• Recomputing each window sum from scratch, turning the algorithm into O(n times k).
• Using prefix sums but indexing with prefix[k - i] off-by-one for the right-side picks.
• Returning the minimum-window sum instead of total - minWindow.

Interview Tips#

• Pitch the inversion explicitly: "I will minimize the middle instead of maximize the ends."
• Draw the array with a sliding window of size n - k on the whiteboard.
• Mention the brute-force O(k) two-pointer approach as a sanity check, then upgrade to O(n).
• Watch for k == n and k == 1 edge cases out loud.
• Discuss the prefix-sum alternative briefly so the interviewer sees breadth.

Follow-up Questions#

• How would you solve it with prefix sums only? Compute prefix and suffix sums, then iterate splits.
• What if you could take any k cards, not just from ends? It becomes "pick top-k", solved with a heap or quickselect.
• What if values can be negative? Same algorithm, but minimum-window sum can be negative.
• What if k is very small relative to n? The original O(k) two-pointer over splits is faster in practice.
• How would you parallelize on huge arrays? Split into chunks, compute partial window sums, merge boundary windows.

Key Takeaways#

• LeetCode 1423 — Maximum Points You Can Obtain from Cards solves in O(n) time and O(1) space.
• Picking from both ends with fixed count maps to a fixed-size minimum-window problem on the middle.
• The transformation: max picked sum equals total minus min middle window sum.
• Use a sliding window of size n - k, not k.
• Always handle k == n as the trivial case before sliding.
• Asked at Google, Amazon, Meta, and Stripe in array and sliding window rounds.
• The same complement trick extends to any "remove suffix/prefix" optimization.