Published in

Nerd For Tech

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

`Input: cardPoints = [1,2,3,4,5,6,1], k = 3Output: 12Explanation: 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!!

--

--

## More from Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.