Maximum Points You Can Obtain from Cards - Solution & Explanation
Problem Statement
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.length
Approach Overview
Problem 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 1: Sliding Window to Minimize Unused Cards
The primary observation is that by taking k cards from either end, you are essentially leaving n-k cards behind. Thus, instead of focusing on maximally acquiring k cards, focus on finding the minimum sum of n-k cards that are left unused.
Calculate the total sum of card points, then utilize a sliding window of size n-k to find the minimum sum of that window. Finally, subtract this minimum sum from the total sum to get the maximum score you can obtain by taking k cards.
The function calculates the total sum of the array and then finds the minimal sum of any subarray of length n-k using a sliding window. This sliding window allows us to efficiently find which elements to leave behind, thus maximizing the cards taken. The remaining cards' minimum sum is subtracted from the total to give the optimal score.
Complexity
Time Complexity: O(n), where n is the length of cardPoints, because we traverse the list once for the sliding window.
Space Complexity: O(1), as no additional space proportional to the input size is used.
Approach 2: Prefix and Suffix Sums
This approach involves calculating the prefix sums from the start and suffix sums from the end of the cardPoints array. By doing so, you can easily compute what the score would be when selecting a certain number of cards from the start and remaining cards from the end, iterating such that the using combinations of these selections.
A loop over k possible selections computes maximum scores from k elements chosen such that some are prefix and the rest are suffix.
The C++ solution involves initiating prefix and suffix arrays that hold summed values progressively such that each index i in either array holds the sum of the first i or last i elements of the main array. Then a loop is used to check each possible distribution of cards between prefix and suffix to find and combine the maximum scores achievable with k moves.
Complexity
Time Complexity: O(k), because we are computing prefix and suffix sums for k cards and then comparing these sums k times.
Space Complexity: O(k), due to the storage of prefix and suffix sums in two arrays of length k.
Approach 3: Sliding Window
We can use a sliding window of length k to simulate this process.
Initially, we place the window at the end of the array, i.e., the k positions from index n-k to index n-1. The sum of the points of the cards in the window is denoted as s, and the initial value of the answer ans is also s.
Next, we consider the situation where we take 1, 2, ..., k cards from the beginning of the array in turn. Suppose the card taken is cardPoints[i]. Then we add it to s. Due to the length limit of the window is k, we need to subtract cardPoints[n-k+i] from s. In this way, we can calculate the sum of the points of the k cards taken and update the answer ans.
The time complexity is O(k), where k is the integer given in the problem. The space complexity is O(1).
Code
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window to Minimize Unused Cards | Time Complexity: O(n), where n is the length of cardPoints, because we traverse the list once for the sliding window. Space Complexity: O(1), as no additional space proportional to the input size is used. |
| Prefix and Suffix Sums | Time Complexity: O(k), because we are computing prefix and suffix sums for k cards and then comparing these sums k times. Space Complexity: O(k), due to the storage of prefix and suffix sums in two arrays of length k. |
| Sliding Window | — |
Detailed Complexity Analysis
| 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 |
Video Solution
L2. Maximum Points You Can Obtain from Cards | 2 Pointers and Sliding Window Playlist • take U forward • 357,713 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Points You Can Obtain from Cards easy or hard?
Maximum Points You Can Obtain from Cards Python/Java solution
How to solve Maximum Points You Can Obtain from Cards in O(n)?
What is the best approach for Maximum Points You Can Obtain from Cards?
Is Maximum Points You Can Obtain from Cards asked at Google/Amazon/Meta?
What data structure is used in Maximum Points You Can Obtain from Cards?
What is the time complexity of Maximum Points You Can Obtain from Cards?
Ready to solve this problem?
Practice Maximum Points You Can Obtain from Cards with our built-in code editor and test cases.
Practice on FleetCode