Problem Description

You have a row of cards, where each card has a point value. These point values are given in an array called cardPoints.

You need to pick exactly k cards from this row, but there's a constraint: you can only pick cards from either the beginning (leftmost) or the end (rightmost) of the row. Each time you pick a card, you can choose to take it from either end.

Your goal is to maximize the total sum of points from the k cards you pick.

For example, if cardPoints = [1, 2, 3, 4, 5, 6, 1] and k = 3, you could:

• Take 3 cards from the beginning: 1 + 2 + 3 = 6
• Take 3 cards from the end: 1 + 6 + 5 = 12
• Take 2 from the beginning and 1 from the end: 1 + 2 + 1 = 4
• Take 1 from the beginning and 2 from the end: 1 + 6 + 5 = 12

The maximum score would be 12.

The function should return the maximum possible score you can achieve by picking exactly k cards following these rules.

Intuition

When we pick k cards from either end of the array, we're essentially choosing some cards from the left end and the remaining cards from the right end. If we take i cards from the left, we must take k - i cards from the right.

The key insight is that the cards we pick will always form a "continuous segment" if we imagine the array as circular. For instance, if we pick 2 cards from the left and 3 cards from the right, we're picking the first 2 elements and the last 3 elements - which would be consecutive if we wrapped the array around.

Instead of trying all possible combinations, we can think of this problem differently: we start by taking all k cards from one end (say, the right end), giving us an initial sum. Then, we can "slide" our selection by replacing cards from the right with cards from the left, one at a time.

For example, if we initially take the last k cards, we can then:

• Replace the leftmost card of our selection (which is cardPoints[n-k]) with cardPoints[0]
• Replace the next card (cardPoints[n-k+1]) with cardPoints[1]
• And so on...

This sliding process allows us to explore all possible ways to pick k cards from both ends efficiently. At each step, we add one card from the left and remove one card from our current right selection, updating our sum and tracking the maximum.

This transforms the problem from "choosing cards from two ends" to "finding the best window of k cards that wraps around the array ends," which can be solved in linear time with a sliding window approach.

Learn more about Prefix Sum and Sliding Window patterns.

Solution Approach

The implementation uses a sliding window technique to efficiently find the maximum score.

Initial Setup: We start by taking all k cards from the right end of the array. This is done by computing sum(cardPoints[-k:]), which gives us the sum of the last k elements. We store this sum in variable s and also initialize our answer ans with this value.

Sliding Process: We then iterate through the first k elements of the array using enumerate(cardPoints[:k]). For each iteration i:

1. Add a card from the left: We add cardPoints[i] (represented as x in the code) to our current sum s.

2. Remove a card from the right: Since we're maintaining exactly k cards, we need to remove one card from our right selection. The card to remove is cardPoints[-k + i]. This index works because:

   • When i = 0: we remove cardPoints[-k] (the leftmost card of our initial right selection)
   • When i = 1: we remove cardPoints[-k + 1] (the next card)
   • And so on...

3. Update the sum: The new sum becomes s = s + x - cardPoints[-k + i]

4. Track the maximum: We update ans = max(ans, s) to keep track of the maximum score seen so far.

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

• Initial: Take last 3 cards: [5, 6, 1], sum = 12
• Iteration 0: Add 1, remove 5 → [1, 6, 1], sum = 8
• Iteration 1: Add 2, remove 6 → [1, 2, 1], sum = 4
• Iteration 2: Add 3, remove 1 → [1, 2, 3], sum = 6
• Maximum score = 12

The time complexity is O(k) since we iterate through at most k elements, and the space complexity is O(1) as we only use a few variables to track the sum and maximum.

Example Walkthrough

Let's walk through a small example to illustrate the sliding window approach.

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

Step 1: Initial Setup

• Start by taking all 3 cards from the right end: [7, 7, 9]
• Initial sum s = 7 + 7 + 9 = 23
• Current maximum ans = 23

Step 2: Sliding Process Now we slide our selection by replacing cards from the right with cards from the left:

Iteration 0 (i=0):

• Add card from left: cardPoints[0] = 9
• Remove card from right: cardPoints[-3 + 0] = cardPoints[-3] = 7 (the leftmost of our right selection)
• New selection: [9] from left + [7, 9] from right
• New sum: s = 23 + 9 - 7 = 25
• Update maximum: ans = max(23, 25) = 25

Iteration 1 (i=1):

• Add card from left: cardPoints[1] = 7
• Remove card from right: cardPoints[-3 + 1] = cardPoints[-2] = 7
• New selection: [9, 7] from left + [9] from right
• New sum: s = 25 + 7 - 7 = 25
• Update maximum: ans = max(25, 25) = 25

Iteration 2 (i=2):

• Add card from left: cardPoints[2] = 7
• Remove card from right: cardPoints[-3 + 2] = cardPoints[-1] = 9
• New selection: [9, 7, 7] from left + [] from right (all from left now)
• New sum: s = 25 + 7 - 9 = 23
• Update maximum: ans = max(25, 23) = 25

Result: The maximum score is 25, achieved by taking 1 card from the left [9] and 2 cards from the right [7, 9].

This sliding window technique efficiently explores all possible combinations of taking cards from both ends in just O(k) time.

Solution Implementation

Time and Space Complexity

The time complexity is O(k), where k is the integer given in the problem. The initial calculation sum(cardPoints[-k:]) takes O(k) time to sum the last k elements. Then the for loop iterates through the first k elements with enumerate(cardPoints[:k]), which also takes O(k) time. Inside the loop, each operation (addition, subtraction, and max comparison) takes O(1) time. Therefore, the overall time complexity is O(k) + O(k) = O(k).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables ans, s, i, and x, regardless of the input size. The slicing operation cardPoints[:k] in the enumerate function creates an iterator that doesn't create a new list in memory, and even if it did create a temporary slice, it would be O(k) which is bounded by the input parameter rather than growing with the size of the cardPoints array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Confusion with Negative Indexing

The Pitfall: A common mistake is getting confused about which card to remove when using cardPoints[-k + i]. Developers often incorrectly think they need to remove cardPoints[-(k - i)] or cardPoints[-k - i - 1], leading to incorrect results or index out of bounds errors.

Why It Happens: The confusion arises from mixing up the relationship between:

• How many cards we're taking from the left (i+1 cards after iteration i)
• Which card from the right selection needs to be removed

The Solution: Remember that -k + i gives us the correct card to remove because:

• Initially, we have cards at indices [-k, -k+1, ..., -2, -1]
• When we add the i-th card from left, we remove the i-th card from our initial right selection
• The i-th card in our right selection is at index -k + i

Visual Example:

# If k=3 and array has 7 elements:
# Initial right selection: indices [-3, -2, -1] → elements at positions [4, 5, 6]
# i=0: Remove index -3+0 = -3 (position 4)
# i=1: Remove index -3+1 = -2 (position 5)
# i=2: Remove index -3+2 = -1 (position 6)

2. Not Considering the Initial State

The Pitfall: Some implementations forget to include the initial state (all k cards from the right) as a potential maximum, starting the sliding window with mixed selections only.

Why It Happens: Developers focus on the "sliding" part and forget that taking all cards from one end is also a valid solution.

The Solution: Always initialize your maximum with the sum of either all k cards from the left or all k cards from the right before starting the sliding process:

# Correct initialization
current_sum = sum(cardPoints[-k:])  # All from right
max_score = current_sum  # Don't forget this!

3. Off-by-One Error in Loop Range

The Pitfall: Using range(k+1) instead of range(k), which would try to take k+1 cards from the left, exceeding the allowed number of cards.

Why It Happens: Confusion about whether the loop represents "number of cards from left" or "number of iterations". Since we start with 0 cards from left, we need exactly k iterations to reach k cards from left.

The Solution: Use range(k) which gives iterations 0 through k-1:

• Iteration 0: 1 card from left, k-1 from right
• Iteration 1: 2 cards from left, k-2 from right
• ...
• Iteration k-1: k cards from left, 0 from right