Maximum Points You Can Obtain from Cards | Leetcode 1423

The problem “Maximum Points You Can Obtain from Cards” asks you to pick exactly k cards from either the start or the end of the array cardPoints to maximize the total points. The key insight is that if you must pick k cards from the ends, then you’re effectively choosing some from the left prefix and the rest from the right suffix, and you can try all splits in O(k) after a couple of passes.

Here’s the [Problem Link] to begin with.

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.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Constraints:

• 1 <= cardPoints.length <= 105
• 1 <= cardPoints[i] <= 104
• 1 <= k <= cardPoints.length

Optimal Solution: Enumerate Left/Right Split in O(k)

Why this works

Picking from ends is equivalent to leaving a middle subarray of length n - k unpicked. The complementary viewpoint: the maximum you can pick equals the total sum minus the minimum sum subarray of length n - k. The provided method is an equivalent and intuitive approach that directly builds left and right sums as you slide how many you take from each side.

Code

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        """If k equals the length of the cardPoints,
        the maximum points are achieved by picking all cards.
        TC - O(N) (sum() function takes N time, where N is len cardPoints)
        SC - O(1), No extra space used."""
        if k == len(cardPoints):
            return sum(cardPoints)

        max_sum = 0
        left_sum = 0
        right_sum = 0
        n = len(cardPoints)
        # Take all k from the left initially
        for i in range(k):
            left_sum += cardPoints[i]
        max_sum = left_sum

        # Slide: give back from left, take from right
        right_index = n - 1
        for i in range(k - 1, -1, -1):
            left_sum -= cardPoints[i]          # remove one from the left window
            right_sum += cardPoints[right_index]  # add one from the right tail
            right_index -= 1
            max_sum = max(max_sum, left_sum + right_sum)
        return max_sum

Step-by-Step Explanation

1. Edge case: If k == n, picking all cards is optimal → return sum(cardPoints).
2. Initialize with all-left pick: Sum the first k cards into left_sum; set max_sum = left_sum.
3. Iteratively swap picks: For each iteration t from 1 to k:
   • Remove the last included left card from left_sum (shrink left window by 1).
   • Add one more card from the right end into right_sum.
   • Update max_sum with left_sum + right_sum.
4. The loop explores all splits:
   • x left and (k−x) right for x = k, k−1, …, 0.
5. Return max_sum.

Dry Run (Quick)

• cardPoints = , k = 3
  • Start with left 3: left_sum = 1+2+3 = 6, max_sum=6
  • Move 1 from left to right: left_sum=6−3=3, right_sum=1 → 3+1=4 → max=6
  • Move another: left_sum=3−2=1, right_sum=1+6=7 → 1+7=8 → max=8
  • Move last: left_sum=1−1=0, right_sum=7+5=12 → 12 → max=12
    Answer: 12

This matches the known optimal choice: pick 6 and 5 from right, and 1 from left → total 12.

Complexity

• Time:
  • Initial left sum: O(k)
  • Sliding k times: O(k)
  • Total: O(k) (plus O(1) checks), which is excellent when k ≤ n.
• Space: O(1) – only a handful of variables.

Alternative View: Minimum Window to Skip

• Another elegant approach: With total sum S, the maximum pick of k cards equals S − minSumWindow(n − k).
• Use a sliding window of length n − k to find the minimum sum window to skip.
• Equivalent in result; the provided implementation is often more intuitive.

Tips and Edge Cases

• k = 0 → result should be 0 (pick no cards).
• k = n → result is sum(cardPoints).
• Works for all non-negative card values; if negatives were allowed, the logic still holds since we control left/right picks explicitly.
• Watch out for off-by-one in indices; use clear variable names like right_index.

Takeaway

This problem is a classic example of picking from ends with a fixed count. The optimal strategy enumerates how many to take from the left versus the right in O(k) and keeps a running best. It’s clean, efficient, and extremely interview-friendly.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.