LeetCode 1423. Maximum Points You Can Obtain from Cards 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 cards.
Your score is the sum of the points of the cards you have taken.
Given the integer array cardPoints
and the integer , return the maximum score you can obtain.
Example 1:
Input: cardPoints = [1,2,3,4,5,6,1]
, k = 3
Output:
Explanation: After the first step, your score will always be . 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 .
Example 2:
Input: cardPoints = [2,2,2]
, k = 2
Output:
Explanation: Regardless of which two cards you take, your score will always be .
Example 3:
Input: cardPoints = [9,7,7,9,7,7,9]
, k = 7
Output:
Explanation: You have to take all the cards. Your score is the sum of points of all cards.
Constraints:
-
cardPoints.length
-
cardPoints[i]
-
cardPoints.length
Problem Link: https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/
Solution
Brute Force
First, we can make the observation that there are only different choices of cards if we take exactly cards. Let's assume we took exactly cards from the left. The number of cards we take from the right will be fixed as we'll take cards on the right to reach a total of cards.
For each choice of cards, we can just iterate through the cards and find the sum. To find the maximum sum, we'll repeat this process for all choices. This solution will run in .
Full Solution
Let's look at two different choices of cards. The first choice will be to take cards from the left and cards from the right. The second choice will be to take cards from the left and 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 instead of .
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 cards on the left and card on the right. Our second choice will consist of card on the left and cards on the right.
The sum with our first choice is currently . 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 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 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 cards are picked from the right.
Time Complexity
We'll require to calculate the sum for the first choice. In addition, it will take another process all choices. Thus, our final time complexity will be .
Time Complexity: .
Space Complexity
Since we use two pointers to maintain the sum of every choice, our space complexity is .
Space Complexity: .
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