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

Maximum Points You Can Obtain from Cards

Medium ArrayTwo Pointers LeetCode

A row of cards is laid out in front of you, each worth some number of points. On each turn you can grab a card only from the front or the back of the row, and you must grab exactly k cards in total. Your score is the sum of the points on the cards you've collected. Return the highest score achievable.

Input Format
Implement maxScore(cardPoints, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
cardPoints = [1,2,3,4,5,6,1]
k = 3
Output
12

Example 2

Input
cardPoints = [1,2,3]
k = 3
Output
6
Constraints
  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length
Test Cases (2)
Case 1
Args: [[1,2,3,4,5,6,1],3] Expected: 12
Case 2
Args: [[1,2,3],3] Expected: 6
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.

javascript
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