LeetCode 1423 - Maximum Points You Can Obtain from Cards

The problem asks us to maximize the total points we can collect from a row of cards, where each card has a point value.

leetcodemediumarraysliding-windowprefix-sum

LeetCode Problem 1423

Difficulty: 🟡 Medium
Topics: Array, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to maximize the total points we can collect from a row of cards, where each card has a point value. You are allowed to pick exactly k cards, and each pick must come from either the beginning or end of the row. The goal is to compute the largest possible sum obtainable by making these selections.

The input consists of an integer array cardPoints, representing the points on each card, and an integer k, representing the total number of cards to take. The output is a single integer representing the maximum sum achievable.

Constraints tell us that the length of cardPoints can be up to 100,000 and each card's point value can be up to 10,000. This indicates that an inefficient solution, such as one that tries all combinations of left and right picks in a brute-force manner, will be too slow due to exponential complexity.

Important edge cases include when k equals the length of the array (take all cards), when all card values are identical, and when k is 1 or the array has only one card. The problem guarantees at least one card and that k is always valid, so we do not need to handle empty arrays or invalid k.

Approaches

The brute-force approach would iterate through every possible combination of taking i cards from the left and k-i cards from the right for all i from 0 to k. For each combination, we compute the sum of selected cards and track the maximum. This approach is correct but inefficient because it requires O(k) work for each of the k combinations, resulting in O(k^2) time complexity. For k up to 100,000, this is infeasible.

The optimal approach relies on the observation that taking k cards from the ends is equivalent to leaving a contiguous subarray of length n-k somewhere in the middle unpicked. Instead of trying all combinations of left and right picks, we can find the subarray of length n-k with the minimum sum, because the total score is totalSum - minSubarraySum. This is efficient because it only requires a single pass to compute prefix sums or use a sliding window to find the minimum sum subarray.

Approach Time Complexity Space Complexity Notes
Brute Force O(k^2) O(1) Try every combination of left/right picks
Optimal O(n) O(1) Use sliding window to find min subarray sum of length n-k

Algorithm Walkthrough

  1. Compute the total sum of all cards. This represents the maximum score if we could take all cards.
  2. Determine the length of the subarray to leave unpicked: n - k, where n is the length of cardPoints.
  3. Use a sliding window of length n - k to find the minimum sum of any contiguous subarray of that length. Initialize the window sum with the first n - k elements and slide it across the array, updating the sum and tracking the minimum.
  4. Subtract the minimum subarray sum from the total sum. This gives the maximum score achievable by taking k cards from the ends.
  5. Return the result.

Why it works: The problem reduces to leaving the smallest possible block in the middle unpicked. Since we are constrained to pick from the ends, the maximum sum comes from excluding the minimal middle subarray. This property guarantees optimality.

Python Solution

from typing import List

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        total_sum = sum(cardPoints)
        window_size = n - k
        
        if window_size == 0:
            return total_sum
        
        current_sum = sum(cardPoints[:window_size])
        min_window_sum = current_sum
        
        for i in range(window_size, n):
            current_sum += cardPoints[i] - cardPoints[i - window_size]
            min_window_sum = min(min_window_sum, current_sum)
        
        return total_sum - min_window_sum

The code first calculates the total points, then uses a sliding window to find the minimum subarray sum of length n - k. By subtracting this minimal sum from the total, we obtain the maximum achievable score.

Go Solution

func maxScore(cardPoints []int, k int) int {
    n := len(cardPoints)
    totalSum := 0
    for _, val := range cardPoints {
        totalSum += val
    }
    
    windowSize := n - k
    if windowSize == 0 {
        return totalSum
    }
    
    currentSum := 0
    for i := 0; i < windowSize; i++ {
        currentSum += cardPoints[i]
    }
    minWindowSum := currentSum
    
    for i := windowSize; i < n; i++ {
        currentSum += cardPoints[i] - cardPoints[i - windowSize]
        if currentSum < minWindowSum {
            minWindowSum = currentSum
        }
    }
    
    return totalSum - minWindowSum
}

In Go, we handle slices similarly to Python lists. Integer overflow is not a concern here given the constraints. The sliding window logic is directly translated from Python.

Worked Examples

Example 1: cardPoints = [1,2,3,4,5,6,1], k = 3

Total sum = 22, window size = 7 - 3 = 4.

Sliding window sums of length 4: [1+2+3+4=10, 2+3+4+5=14, 3+4+5+6=18, 4+5+6+1=16]

Minimum sum = 10

Maximum score = 22 - 10 = 12

Example 2: cardPoints = [2,2,2], k = 2

Total sum = 6, window size = 3 - 2 = 1

Sliding window sums: [2,2,2]

Minimum sum = 2

Maximum score = 6 - 2 = 4

Example 3: cardPoints = [9,7,7,9,7,7,9], k = 7

Window size = 0, so we take all cards.

Maximum score = sum = 55

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to compute total sum and sliding window
Space O(1) Only a few variables used, no extra data structures

The algorithm is efficient for the upper bound of n = 10^5.

Test Cases

# Provided examples
assert Solution().maxScore([1,2,3,4,5,6,1], 3) == 12  # mix of left/right picks
assert Solution().maxScore([2,2,2], 2) == 4  # identical values
assert Solution().maxScore([9,7,7,9,7,7,9], 7) == 55  # take all cards

# Edge cases
assert Solution().maxScore([1], 1) == 1  # single card
assert Solution().maxScore([1,1000,1], 1) == 1_000  # choosing the best end
assert Solution().maxScore([100,40,17,9,73,75], 3) == 248  # example requiring both ends
assert Solution().maxScore([1,79,80,1,1,1,200,1], 4) == 382  # tricky distribution
Test Why
[1,2,3,4,5,6,1], k=3 Validates mix of left/right picks
[2,2,2], k=2 All values identical, any pick is same
[9,7,7,9,7,7,9], k=7 Must pick all cards
[1], k=1 Single element edge case
[1,1000,1], k=1 Picking optimal end
[100,40,17,9,73,75], k=3 Requires combination of left and right
[1,79,80,1,1,1,200,1], k=4 Complex distribution needing careful sliding window

Edge Cases

Single-element array: If cardPoints has only one element, the maximum score is trivially the element itself. Both Python and Go solutions handle this because the total sum calculation and window size logic correctly return the total sum.

k equals array length: If k equals n, the algorithm correctly returns the sum of all cards since the window size n - k becomes zero, and the early return handles it efficiently.

All cards have the same value: In this case, the minimum sum subarray is identical to any subarray of length n-k, so the algorithm naturally computes the correct result. No special handling is needed, but it is an important test to ensure that min calculations do not introduce off-by-one errors.