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 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
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
Which of the following uses divide and conquer strategy?
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Solution Implementation
Breadth first search can be used to find the shortest path between two nodes in a directed graph.
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching 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.