Question:

You are given an integer array cardPoints representing the number of points on each card. You start at the beginning of the array and can take any k cards from the front or the back. However, you must take exactly k cards.

Your task is to find the maximum number of points you can obtain from these cards.

Write a function maxPoints(cardPoints: List[int], k: int) -> int to solve the problem.

Example

cardPoints = [1,2,3,4,5,6,1]
k = 3
maxPoints(cardPoints, k) => 12

Constraints

• The number of cards n will be between 1 and 10^5.
• Each card will have a value between 1 and 10^4.
• The value of k will be between 1 and n.

Answer:

To solve this problem, we can use the sliding window technique. The idea is to maintain a window of k cards and slide it from left to right, while keeping track of the maximum sum of points encountered so far.

Here is a step-by-step explanation of the algorithm:

1. Initialize two pointers, left and right, both pointing to the beginning of the array.
2. Set the initial sum of points to 0.
3. Move the right pointer k steps ahead, summing up the points encountered along the way.
4. Initialize the maximum sum of points as the current sum of points.
5. While the right pointer is within the array bounds:
   • Subtract the points of the card at position left from the current sum of points.
   • Move the left pointer one step to the right.
   • Add the points of the card at position right to the current sum of points.
   • Move the right pointer one step to the right.
   • Update the maximum sum of points if the current sum of points is greater.
6. Return the maximum sum of points.

Here is the implementation of the solution in Python:

def maxPoints(cardPoints, k):
    n = len(cardPoints)
    left = 0
    right = k - 1
    currSum = sum(cardPoints[left:right+1])  # initial sum of first k cards
    maxSum = currSum
    
    while right < n-1:  # slide the window to the right
        currSum -= cardPoints[left]
        left += 1
        right += 1
        currSum += cardPoints[right]
        maxSum = max(maxSum, currSum)
    
    return maxSum

The time complexity of this solution is O(n), where n is the length of the cardPoints array. This is because we iterate through the array only once to compute the maximum sum of points.