1423. Maximum Points You Can Obtain from Cards

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 kk cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer kk, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 1212
Explanation: After the first step, your score will always be 11. 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=121 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 44
Explanation: Regardless of which two cards you take, your score will always be 44.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 5555
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Constraints:

  • 11\leq cardPoints.length 105\leq 10^5
  • 11\leq cardPoints[i] 104\leq 10^4
  • 1k1 \leq k \leq cardPoints.length

Solution

Brute Force

First, we can make the observation that there are only O(K)\mathcal{O}(K) different choices of cards if we take exactly KK cards. Let's assume we took exactly LL (0LK)(0\leq L\leq K) cards from the left. The number of cards we take from the right will be fixed as we'll take KLK-L cards on the right to reach a total of KK cards.

For each choice of KK cards, we can just iterate through the KK cards and find the sum. To find the maximum sum, we'll repeat this process for all O(K)\mathcal{O}(K) choices. This solution will run in O(K2)\mathcal{O}(K^2).

Full Solution

Let's look at two different choices of KK cards. The first choice will be to take LL cards from the left and KLK-L cards from the right. The second choice will be to take L1L-1 cards from the left and KL+1K-L+1 cards from the right. Instead of recalculating the sum for the second choice, we can adjust the sum from the first choice to be the second choice. We can notice that the difference between these two choices is that we added a card on the right side and we removed a card from the left side. By applying these changes, we can transition between two choices in O(1)\mathcal{O}(1) instead of O(K)\mathcal{O}(K).

Example

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

Let's look at the transition between two different choices in this example. Our first choice consists of 22 cards on the left and 11 card on the right. Our second choice will consist of 11 card on the left and 22 cards on the right.

The sum with our first choice is currently 44. Going from our first choice to our second choice, our left side lost a card and our right side gained a card. Specifically, we lost cardPoints[1] = 2 and we gained cardPoints[5] = 6. After removing cardPoints[1] and adding cardPoints[5], we obtain a sum of 88 for our second choice.

We can implement this with the idea of two pointers. We'll use the pointers to indicate which cards we picked on the left and right side. A simple way to implement this with two pointers is to start with picking all KK cards on the left. For each transition, we'll remove one card on the left and add one card on the right. We keep repeating this process until we reach the choice where all our KK cards are picked from the right.

Time Complexity

We'll require O(K)\mathcal{O}(K) to calculate the sum for the first choice. In addition, it will take another O(K)\mathcal{O}(K) process all O(K)\mathcal{O}(K) choices. Thus, our final time complexity will be O(K)\mathcal{O}(K).

Time Complexity: O(K)\mathcal{O}(K).

Space Complexity

Since we use two pointers to maintain the sum of every choice, our space complexity is O(1)\mathcal{O}(1).

Space Complexity: O(1)\mathcal{O}(1).

C++ Solution

1class Solution {
2   public:
3    int maxScore(vector<int>& cardPoints, int k) {
4        int n = cardPoints.size();
5        int leftSum = 0;
6        for (int i = 0; i < k;
7             i++) {  // calculate sum where all cards on the left side
8            leftSum += cardPoints[i];
9        }
10        int rightSum = 0;
11        int rightIndex = n;  // pointer for the right cards
12        int ans = leftSum;
13        for (int leftIndex = k - 1; leftIndex >= 0;
14             leftIndex--) {                    // pointer for the left cards
15            leftSum -= cardPoints[leftIndex];  // transition between choices
16            rightIndex--;
17            rightSum += cardPoints[rightIndex];
18            ans = max(ans, leftSum + rightSum);
19        }
20        return ans;
21    }
22};

Java Solution

1class Solution {
2    public int maxScore(int[] cardPoints, int k) {
3        int n = cardPoints.length;
4        int leftSum = 0;
5        for (int i = 0; i < k;
6             i++) { // calculate sum where all cards on the left side
7            leftSum += cardPoints[i];
8        }
9        int rightSum = 0;
10        int rightIndex = n; // pointer for the right cards
11        int ans = leftSum;
12        for (int leftIndex = k - 1; leftIndex >= 0;
13             leftIndex--) { // pointer for the left cards
14            leftSum -= cardPoints[leftIndex]; // transition between choices
15            rightIndex--;
16            rightSum += cardPoints[rightIndex];
17            ans = Math.max(ans, leftSum + rightSum);
18        }
19        return ans;
20    }
21}

Python Solution

1class Solution:
2    def maxScore(self, cardPoints: List[int], k: int) -> int:
3        n = len(cardPoints)
4        leftSum = 0
5        for i in range(k):  # calculate sum where all cards on the left side
6            leftSum += cardPoints[i]
7        rightSum = 0
8        rightIndex = n  # pointer for the right cards
9        ans = leftSum
10        for leftIndex in range(k - 1, -1, -1):  # pointer for the left cards
11            leftSum -= cardPoints[leftIndex]  # transition between choices
12            rightIndex -= 1
13            rightSum += cardPoints[rightIndex]
14            ans = max(ans, leftSum + rightSum)
15        return ans
16
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Solution Implementation


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄