Problem Description

You are given an integer array cardPoints and an integer k. The array represents a row of cards, each with some points on it. Your task is to pick exactly k cards from either the start or the end of the array (you can pick from either end in any order), and maximize the total points you can obtain from these cards.

Constraints:

• You must pick exactly k cards in total.
• You can only pick from the beginning or the end of the array, not from the middle.
• Each card can only be chosen once.
• There is always at least one valid solution.

Example:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: Pick the cards with values 6, 5, and 1 (either the last three or first two and last one).

Thought Process

At first glance, the problem seems to ask for the maximum sum by choosing k cards from either end of the array. A brute-force approach would be to try all possible combinations of picking cards from the start and end, but this quickly becomes inefficient as the number of combinations grows exponentially with k.

Instead, we need an optimized method. Notice that for each way of picking cards, you can pick some cards from the front and the rest from the back, and the total number of picked cards is always k. So, for each possible split (i.e., pick i cards from the front and k-i cards from the back), we can compute the sum and keep track of the maximum.

By shifting our perspective to think in terms of which cards remain unpicked, we can further optimize the solution. Since you always pick k cards, you leave behind a contiguous subarray of length n - k. If we find the minimum sum of any such contiguous subarray, subtracting it from the total sum gives the maximum points obtainable.

Solution Approach

Let's break down the optimized approach step by step:

1. Compute the total sum of all cards. This represents the sum if you picked all cards.
2. Find the subarray of length n - k with the minimum sum.
   • This subarray represents the cards you do not pick.
   • We use a sliding window of size n - k to efficiently find the minimum sum.
3. Subtract the minimum subarray sum from the total sum.
   • This gives the maximum points you can obtain by picking k cards from the ends.

Why use a sliding window? Because it lets us compute all possible sums of contiguous subarrays of a given length in linear time, which is much faster than checking every possible combination.

Example Walkthrough

Let's use the sample input: cardPoints = [1,2,3,4,5,6,1], k = 3.

1. Total sum: 1 + 2 + 3 + 4 + 5 + 6 + 1 = 22
2. Length of subarray not picked: n - k = 7 - 3 = 4
3. Find the minimum sum of any contiguous subarray of length 4:
   • Subarray [1,2,3,4] sum = 10
   • Subarray [2,3,4,5] sum = 14
   • Subarray [3,4,5,6] sum = 18
   • Subarray [4,5,6,1] sum = 16
   • Minimum is 10
4. Maximum points: 22 - 10 = 12
5. Interpretation: The optimal strategy is to leave out the subarray [1,2,3,4], and pick the last three cards [5,6,1] for a total of 12 points.

Time and Space Complexity

Brute-force approach: For each possible combination of picking cards from the front and back (from 0 to k cards from the front), compute the sum. This requires O(k) computations, and each computation takes O(k) time, so overall O(k^2) time.

Optimized sliding window approach:

• Computing the total sum: O(n)
• Finding the minimum subarray sum with a sliding window: O(n)
• Total time complexity: O(n)
• Space complexity: O(1) (only a few variables are needed)

Here, n is the length of cardPoints.

Summary

The key insight is to reframe the problem: instead of focusing on which k cards to pick, focus on which n - k contiguous cards to leave behind. By using a sliding window to find the minimal sum of the subarray left behind, we can subtract this from the total sum to get the answer efficiently. This approach is both elegant and efficient, running in linear time and using constant space.

Code Implementation

class Solution:
    def maxScore(self, cardPoints, k):
        n = len(cardPoints)
        total = sum(cardPoints)
        window = n - k
        if window == 0:
            return total
        min_subarray = curr_sum = sum(cardPoints[:window])
        for i in range(window, n):
            curr_sum += cardPoints[i] - cardPoints[i - window]
            min_subarray = min(min_subarray, curr_sum)
        return total - min_subarray
      

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        int total = 0;
        for (int x : cardPoints) total += x;
        int window = n - k;
        if (window == 0) return total;
        int curr_sum = 0;
        for (int i = 0; i < window; ++i)
            curr_sum += cardPoints[i];
        int min_subarray = curr_sum;
        for (int i = window; i < n; ++i) {
            curr_sum += cardPoints[i] - cardPoints[i - window];
            min_subarray = min(min_subarray, curr_sum);
        }
        return total - min_subarray;
    }
};
      

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int total = 0;
        for (int x : cardPoints) total += x;
        int window = n - k;
        if (window == 0) return total;
        int currSum = 0;
        for (int i = 0; i < window; i++)
            currSum += cardPoints[i];
        int minSubarray = currSum;
        for (int i = window; i < n; i++) {
            currSum += cardPoints[i] - cardPoints[i - window];
            minSubarray = Math.min(minSubarray, currSum);
        }
        return total - minSubarray;
    }
}
      

var maxScore = function(cardPoints, k) {
    let n = cardPoints.length;
    let total = cardPoints.reduce((a, b) => a + b, 0);
    let window = n - k;
    if (window === 0) return total;
    let currSum = 0;
    for (let i = 0; i < window; i++)
        currSum += cardPoints[i];
    let minSubarray = currSum;
    for (let i = window; i < n; i++) {
        currSum += cardPoints[i] - cardPoints[i - window];
        minSubarray = Math.min(minSubarray, currSum);
    }
    return total - minSubarray;
};