Problem Breakdown
We are given an array cardPoints and an integer k. We must select exactly k cards from either end of the row to maximize their point sum. Since we take cards from the left, we implicitly leave cards in a contiguous middle subarray (where ). Maximizing the taken points is equivalent to minimizing the remaining points in that specific window size ().
Inputs:
cardPoints: List[int] representing card values. Length .k: int, number of cards to take.
Outputs:
- Integer: Maximum possible score obtained by taking exactly
kcards from ends.
Intuition
A brute-force approach would iterate through all valid combinations ( left, right), calculating the sum for each split point. This results in roughly or time complexity if sums are recalculated naively.
Key Insight: Instead of maximizing the selected cards directly, consider what is left behind. The set of taken cards plus the remaining middle subarray equals the entire array sum. To maximize the score (taken cards), we must equivalently minimize the sum of the cards left in the contiguous middle section. This transforms the problem into finding a minimum sum subarray of fixed length .
Approach
- Calculate Total: Compute
total_sumfor all elements incardPoints. - Handle Edge Case: If
k == n, we take everything, so returntotal_sum. This avoids window logic issues when the remaining count is zero. - Determine Window Size: The number of cards not taken (remaining) is
window_size = n - k. - Sliding Window Initialization: Calculate the sum of the first contiguous subarray of length
window_sizestarting at index 0. Store this inmin_middle_sum. - Slide and Update: Iterate through the array, updating the current window sum by adding the new element entering from the right and subtracting the old element leaving from the left. Track the minimum sum encountered (
min_middle_sum). - Result Calculation: Return
total_sum - min_middle_sum.
Complexity Analysis
- Time Complexity: , where is the length of
cardPoints. We iterate through the array to compute the total sum and then slide a window across it once. Each element is accessed a constant number of times. - Space Complexity: . Only primitive variables (
total_sum,current_window_sum, etc.) are used, independent of input size.
Solution
def maxScore(cardPoints: list[int], k: int) -> int:
n = len(cardPoints)
# Calculate the sum of all cards (baseline total points available)
total_sum = sum(cardPoints)
# If we take all cards, return the total sum immediately.
if k == n:
return total_sum
# The number of elements remaining (not taken) forms a contiguous subarray
window_size = n - k
current_window_sum = 0
# Initialize the first sliding window sum for the 'remaining' cards
for i in range(window_size):
current_window_sum += cardPoints[i]
min_middle_sum = current_window_sum
# Slide the window across the array to find the minimum subarray sum of length (n - k)
# We start sliding from index 'window_size' up to n-1
for i in range(window_size, n):
# Add element entering the window at index i
current_window_sum += cardPoints[i]
# Remove element leaving the window at index i - window_size
current_window_sum -= cardPoints[i - window_size]
# Update minimum sum found so far for the remaining cards
if current_window_sum < min_middle_sum:
min_middle_sum = current_window_sum
return total_sum - min_middle_sum
Edge Cases Handled
- : The code explicitly checks this. If we must take all cards,
window_sizewould be 0. By handling , we avoid iterating over an empty range and correctly return the sum of all elements without needing to subtract a zero-sum window (though mathematically valid). - : The logic holds; it finds the minimum single element in the middle, effectively maximizing one end.
- Small Array: Works for .
- Large Values: Python handles large integers automatically preventing overflow issues common in fixed-width integer languages like C++ or Java (though constraints fit within 32-bit signed int anyway).