Maximum Points You Can Obtain from Cards(Leetcode 1423)

Difficulty: Medium Link: Day 11 : May Leetcode Challenge

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.

Examples

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

Constraints:

  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

Solution

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.

Two Pointer

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?

Sliding Window

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

class Solution {
func maxScore(_ arr: [Int], _ k: Int) -> Int {
let n = arr.count 1
var left = [0], leftSum = 0
var right = [0], rightSum = 0
for i in 0..<k{
leftSum += arr[i]
rightSum += arr[n i]
left.append(leftSum)
right.append(rightSum)
}
var maxSum = 0
for i in 0k {
let currentSum = left[i] + right[k i]
maxSum = max(maxSum,currentSum)
j -= 1
}
return maxSum
}
}

Swift : Sliding Window

class Solution {
func maxScore(_ arr: [Int], _ k: Int) -> Int {
var windowSum = 0
for i in 0..<k {
windowSum += arr[i]
}
var i = k 1, j = arr.count 1
var bestSum = windowSum
while i >= 0 {
windowSum = windowSum + arr[j] arr[i]
bestSum = max(bestSum, windowSum)
i -= 1
j -= 1
}
return bestSum
}
}

Python

class Solution:
def maxScore(self, C: List[int], K: int) -> int:
best = total = sum(C[:K])
for i in range (K1, 1, 1):
total += C[i + len(C) K] C[i]
best = max(best, total)
return best

Java

class Solution {
public int maxScore(int[] C, int K) {
int total = 0;
for (int i = 0; i < K; i++) total += C[i];
int best = total;
for (int i = K 1, j = C.length 1; i >= 0; i, j) {
total += C[j] C[i];
best = Math.max(best, total);
}
return best;
}
}

Complexity Analysis

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)

Links

Sliding Window

Two Pointer

Prefix Sum

Leave a Reply

Your email address will not be published. Required fields are marked *