Watch 10 video solutions for Maximum Points You Can Obtain from Cards, a medium level problem involving Array, Sliding Window, Prefix Sum. This walkthrough by take U forward has 311,927 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= cardPoints[i] <= 1041 <= k <= cardPoints.lengthProblem Overview: You are given an array cardPoints. You must pick exactly k cards from either the start or the end of the array. Each pick adds the card’s value to your score. The goal is to maximize the total points after k picks.
Approach 1: Brute Force Split of Left and Right Picks (O(k^2) time, O(1) space)
One direct way is to try every possible split of picks between the left and right ends. For example, take i cards from the left and k-i from the right for all i from 0 to k. For each combination, recompute the sum of the chosen elements. This approach is easy to reason about but inefficient because each configuration may require summing up to k elements repeatedly. It demonstrates the structure of the problem but does not scale well when k grows.
Approach 2: Prefix and Suffix Sums (O(k) time, O(k) space)
Instead of recomputing sums, precompute prefix sums for the first k elements and suffix sums for the last k elements using a prefix sum technique. Then iterate i from 0 to k, combining prefix[i] (cards taken from the left) with suffix[k-i] (cards taken from the right). Each combination gives the total score for that split. This avoids repeated summation and reduces the complexity significantly while keeping the logic straightforward.
Approach 3: Sliding Window to Minimize Unused Cards (O(n) time, O(1) space)
The key insight: instead of thinking about which k cards you take, think about which n-k cards you leave behind in the middle. If the total sum of the array is known, maximizing the chosen score is equivalent to minimizing the sum of a contiguous subarray of length n-k. Use a sliding window over the array to track the smallest window sum of size n-k. Subtract this minimum from the total array sum to get the maximum obtainable score. The window slides by removing the leftmost element and adding the next element on the right, updating the minimum as you go.
Recommended for interviews: The sliding window solution is what interviewers usually expect. It shows you can reframe the problem and optimize to O(n) time with constant space. The prefix–suffix approach is also acceptable and often easier to implement quickly, while the brute force approach mainly demonstrates the initial reasoning process.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Left/Right Split | O(k^2) | O(1) | For understanding the problem structure or very small k |
| Prefix and Suffix Sums | O(k) | O(k) | When k is small relative to n and simple implementation is preferred |
| Sliding Window (Minimize Middle Subarray) | O(n) | O(1) | Optimal approach for large arrays and typical interview expectations |