Nerd For Tech
Published in

Nerd For Tech

Photo by Dai Yoshinaga on Unsplash

Max point from cards — Daily Challenge May

Today’s question is from Daily Leetcode Coding Challenge — May Edition. It is a medium-tagged question. Let us look into the problem statement.

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

Example

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.

Understanding the problem:

Let us first understand the indexes that are of our interest. We are interested in item 0, 1, 2 … k and n-1, n-2, n-3… n-k. So in the above example our search space is limited to indexes 0, 1, 2 — 4, 5 & 6. In between items does not contribute to solution. Of these indexes we can take 3 and try to maximize. Lets see some selection:

[1, 2 , 3], [1, 2, 1], [1, 1,6], [1, 6, 1] and so on.. only constraint is we can take index 1 unless we also select 0. And same way we can’t select element 6 from right unless we have also taken 1.

In other words we have two extremes selecting k elements from left or selecting k elements from right. All other combination will be by reducing elements from one side and adding elements from other side.

Approach:

Since we have continuity condition while selecting we can using running sum while selecting. We use two pointer approach to achieve this.

We start with from left and select first k elements and get their sum. This will give the sum of points if we select all k elements from left one by one. We place our left pointer at k-1th index and right pointer at the last index here 6.

Now we remove element at index k-1 that is 2 here. This will reduce the left sum by 2. This means we have selected first two elements from left. And points that we have collected 5 points and we are left one more elemnt to be selected. Thats when select the element at n-1th(6th) index. So now total points from k elements is (2+3)5 from left and (1) from right which gives a total of 6. We keep on doing the same till 0th index(inclusive). At that time left sum will become zero and right some become sum of last k elements.

Code implementation:

def maxScore(cardPoints, k):
left_sum = sum(cardPoints[:k])
right_sum = 0
max_points = left_sum + right_sum
lp = k-1
rp = len(cardPoints)-1

while lp >= 0:
left_sum -= cardPoints[lp]
right_sum += cardPoints[rp]
max_points = max(max_points, left_sum + right_sum)

lp -= 1
rp -= 1
return max_points

Complexity Analysis:

  • Time complexity: Since we are using two pointer to go over k elements, complexity is O(k)
  • Space complexity: We have two variables to track the left and right sum. So this solution is solved in constant space.

Happy coding!!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Amit Singh Rathore

Amit Singh Rathore

Staff Data Engineer — Writes about Cloud | Big Data | ML