Difficulty: Medium Link: Day 11 : May Leetcode Challenge
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
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.
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.
Input: cardPoints = [2,2,2], k = 2 Output: 4 Explanation: Regardless of which two cards you take, your score will always be 4.
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.
Input: cardPoints = [1,1000,1], k = 1 Output: 1 Explanation: You cannot take the card in the middle. Your best score is 1.
Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3 Output: 202
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
The problem might look like taking the k maximum values however, but twist is that we can take values either from both ends. So we will be taking total k values anyways either from the left or from the right.
We can take only k values, so either these values can be left, or from right ,or some values from left and rest from right but the total number of values would be k. We can create a Prefix Sum of both K values from left and right side. Then we can follow the two pointer technique to iterate over the possible combinations of values from both ends. Initially we take 0 values from left and k sum of values from right, then 1 values from left and k – 1 from right until we reach left k values and 0 right values. We can keep a track of the max sum possible using a variable and updating the max value. The complexity of the solution would be O(K) and since we are saving prefix sum, O(K) extra space would be needed.
Can we do better?
We can use Sliding Window technique to optimise our solution. The time taken is order of O(K) which we can not reduce it further, however we can still reduce the space complexity. We can keep a track of the sliding window and instead of tracking k elements , we can keep track of n – k elements. We can then move this window k times to cover the entire array and keep track of the window sum by adding new value next and subtracting old value going out of window.
var windowSum windowSum += newValue - oldValue
Swift : Two Pointers with Prefix Sum
Swift : Sliding Window
We are using a sliding window protocol of size n – k. This will iterate about k times to the entire array or O(K). Space is constant since we are just using some variables to track sum.
Time = O(K)
Space = O(1)