Maximum Points You Can Obtain from Cards Medium 0 attempts
LeetCode ↗

Maximum Points You Can Obtain from Cards

Medium ArrayTwo Pointers LeetCode

There are several cards arranged in a row, and each card has an associated number of points. 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. Return the maximum score you can obtain.

Sample Input
cardPoints = [1,2,3,4,5,6,1], k = 3
Sample Output
12
Constraints
  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length
Test Cases
Case 1
Args: [[1,2,3,4,5,6,1],3] Expected: 12
Topics
ArrayTwo Pointers

Taking k cards from the ends is equivalent to leaving a contiguous subarray of size n - k in the middle. To maximize the points from the k cards, minimize the sum of the middle n - k cards using a sliding window.

function maxScore(cardPoints, k) {
  const n = cardPoints.length;
  const windowSize = n - k;
  let windowSum = 0;

  for (let i = 0; i < windowSize; i++) {
    windowSum += cardPoints[i];
  }

  let minWindowSum = windowSum;
  const totalSum = cardPoints.reduce((a, b) => a + b, 0);

  for (let i = windowSize; i < n; i++) {
    windowSum += cardPoints[i] - cardPoints[i - windowSize];
    minWindowSum = Math.min(minWindowSum, windowSum);
  }

  return totalSum - minWindowSum;
}

Time: O(n) Space: O(1)

Saved in this browser only. Private to you.

JavaScript