Skip to main content

1423 - Maximum Points You Can Obtain from Cards

Difficulty: Medium | Pattern: Sliding Window | Company tags: Amazon, Google, Facebook

Problem Statement​

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: Take [6,1] from right and [1] from... wait: take 3 rightmost: [5,6,1]=12 ✓

Example 2:

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

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55

Approach: Sliding Window on Middle — O(n)​

Key insight: We take k cards from the left and/or right. Equivalently, we leave a contiguous subarray of size n-k untouched. To maximize points taken, minimize the sum of the untouched window.

Algorithm Flow​

def maxScore(cardPoints: list[int], k: int) -> int:
    n = len(cardPoints)
    window_size = n - k
    
    if window_size == 0:
        return sum(cardPoints)
    
    # Find minimum sum window of size (n-k)
    window_sum = sum(cardPoints[:window_size])
    min_window = window_sum
    
    for i in range(window_size, n):
        window_sum += cardPoints[i] - cardPoints[i - window_size]
        min_window = min(min_window, window_sum)
    
    return sum(cardPoints) - min_window

Dry Run​

cardPoints = [1,2,3,4,5,6,1], k=3, window_size = 7-3 = 4

WindowSum
[1,2,3,4]10
[2,3,4,5]14
[3,4,5,6]18
[4,5,6,1]16

min_window = 10, total = 22, answer = 22-10 = 12 ✓

Alternative: Prefix Approach​

def maxScore(cardPoints: list[int], k: int) -> int:
    total = sum(cardPoints)
    n = len(cardPoints)
    # Try all splits: take i from left, k-i from right
    left_sum = sum(cardPoints[:k])
    max_score = left_sum
    
    for i in range(k-1, -1, -1):
        left_sum -= cardPoints[i]
        right_sum = sum(cardPoints[n-(k-i):]) if i < k else 0
        max_score = max(max_score, left_sum + right_sum)
    
    return max_score

Edge Cases​

  • k = n → take all cards
  • k = 1 → take either first or last card (max of both)

Complexity​

  • Time: O(n) — one pass for total, one pass for sliding window
  • Space: O(1)

Key Terms​

TermDefinition
Sliding windowA window of fixed or variable size moved across an array to avoid recomputation.
Complement windowThe "leftover" middle subarray of size n-k that is NOT taken; minimizing it maximizes the taken sum.
Prefix sumRunning total used to compute subarray sums in O(1) after O(n) preprocessing.
Two-pointer techniqueUsing left/right indices to expand/shrink a range in a single pass.
Fixed-size windowA window whose length stays constant (n-k here) as it slides, updated by add-one/drop-one.

FAQ​

Q1: Can this be solved without extra space? Yes. Both the sliding-window and prefix-split approaches use O(1) extra space — only running sums and a min/max tracker are needed, no auxiliary arrays.

Q2: What if k equals n? Then window_size = 0, meaning no cards are left untouched — take every card, so the answer is simply sum(cardPoints). The code handles this as a base case.

Q3: Why does minimizing the middle window maximize the picked sum? Because total = taken + untouched, and total is fixed. Since taken = total - untouched, maximizing taken is equivalent to minimizing untouched, and the untouched region is always a contiguous middle block of size n-k given cards are only removed from the ends.

Q4: How would this change if you could take cards from anywhere, not just the ends? It would reduce to selecting the k largest elements (a partial sort or a min-heap of size k), which is a different pattern entirely — no longer a contiguous-window problem.

Q5: What's the time complexity trade-off between the two approaches shown? Both are O(n) time and O(1) space. The sliding-window-on-middle approach is generally considered cleaner because it needs only one pass after the initial window sum, while the prefix/two-sum-split approach explicitly recomputes a right-sum sum inside the loop unless further optimized with prefix arrays.

Quick Revision​

  • Picking k cards from either end leaves a contiguous middle subarray of size n-k untouched.
  • total = sum(cardPoints) is constant; answer = total - min(sum of any window of size n-k).
  • Compute the first window sum, then slide it right: window_sum += cardPoints[i] - cardPoints[i - window_size].
  • Track the minimum window sum seen across the slide.
  • Edge case: k == n → window_size is 0 → answer is total.
  • Edge case: k == 1 → answer is max(cardPoints[0], cardPoints[-1]).
  • Time: O(n) single pass; Space: O(1).
  • Alternative framing: try every split of i cards from the left and k-i from the right, take the max.
  • The core trick — "maximize the taken = minimize the fixed-size complement" — reappears in many two-end selection problems.
  • Same fixed-size sliding window idea: 718-MaximumLengthOfRepeatedSubarray.md
  • Same "pick from both ends" family: pattern also appears in Stone Game / Predict the Winner style DP problems (interval DP), useful to contrast against this greedy sliding-window solution.
  • Variable-size sliding window counterpart: Minimum Size Subarray Sum (LeetCode 209) — same window mechanics but window size grows/shrinks based on a sum threshold instead of being fixed.