Maximum Points You Can Obtain from Cards | Two Pointers and Sliding Window

This chapter explores how to solve the classic "Maximum Points You Can Obtain from Cards" problem using an efficient two-pointer and sliding window approach. Rather than relying on heavy prefix sum arrays, we use dynamic window adjustment to achieve optimal time and space complexity.

1. Problem Statement & Constraints

You are given an array of integers representing the points of $N$ different cards, along with an integer $K$. Your task is to pick exactly $K$ cards from the array and maximize the sum of their points.

The Core Rule

• You must pick cards consecutively from either the front (left) or the back (right) of the array.
• You cannot jump into the middle of the array to pick isolated cards.
• Combinations can mix left and right picks, provided they meet at the boundaries (e.g., $3$ cards from the front and $1$ card from the back).

Example Configuration

Given nums = [6, 2, 3, 4, 7, 2, 1, 7, 1, 2] and K = 4:

• Pick 4 from front: 6 + 2 + 3 + 4 = 15
• Pick 3 from front, 1 from back: 6 + 2 + 3 + 2 = 13
• Pick 2 from front, 2 from back: 6 + 2 + 2 + 1 = 11 (or other variations up to max 16)
• Maximum Possible Sum: 16 (by picking the first 2 elements and the last 2 elements).

2. The Naive Approach vs. The Dynamic Sliding Window

The Extreme Naive Solution

The most direct brute-force approach is to generate all possible valid configurations of picking $K$ elements:

1. Pick $K$ elements from the front, $0$ from the back.
2. Pick $K-1$ from the front, $1$ from the back.
3. Pick $K-2$ from the front, $2$ from the back.
4. ...down to $0$ from the front, $K$ from the back.

By evaluating the sum of each configuration and keeping a running maximum, you will find the answer. However, recalculating sums for every configuration repeatedly leads to inefficient redundant work.

The Optimized Mental Model

Instead of recomputing sums from scratch for every split, imagine starting with all $K$ elements taken entirely from the left side.

• As we shift our strategy, we drop one element from the right side of our left-window and add one element from the extreme right (back) of the array.
• This sliding window adjustment lets us update our sums in $O(1)$ time per step.

3. Step-by-Step Flow Walkthrough

Let's trace how the left and right sums evolve when $K = 4$ for an array:

4. Strategy & Variable Initialization

To implement this cleanly without auxiliary prefix sum arrays, we maintain a few core pointers and tracking variables:

5. Complete Pseudo-Code Implementation

Here is the clean, optimal pseudo-code demonstrating the sliding window subtraction and addition loop:

function maxScore(nums: number[], K: number): number {
    let leftSum = 0;
    let rightSum = 0;
    let n = nums.length;

    // Step 1: Calculate the sum of the first K elements from the left
    for (let i = 0; i < K; i++) {
        leftSum += nums[i];
    }

    let maxSum = leftSum;
    let rightIndex = n - 1;

    // Step 2: Slide the window by removing from left and adding from right
    for (let i = K - 1; i >= 0; i--) {
        // Remove one element from the left window sum
        leftSum -= nums[i];
        
        // Add one element from the back of the array
        rightSum += nums[rightIndex];
        rightIndex--;

        // Update global maximum points
        let currentTotal = leftSum + rightSum;
        if (currentTotal > maxSum) {
            maxSum = currentTotal;
        }
    }

    return maxSum;
}

6. Complexity Analysis

• Time Complexity: $\mathcal{O}(K)$
  • Initializing the left sum takes $\mathcal{O}(K)$ time.
  • The shrinking/expanding loop runs exactly $K$ times, performing constant-time $\mathcal{O}(1)$ operations per iteration.
  • Total Time Complexity: $\mathcal{O}(2K) \approx \mathcal{O}(K)$, which is extremely efficient.
• Space Complexity: $\mathcal{O}(1)$
  • We only utilize a few primitive variables (leftSum, rightSum, maxSum, rightIndex). No extra arrays or hash maps are required.

Summary and Key Takeaways

• Problem Core: Picking $K$ consecutive cards from either extreme ends (front or back) of an array to maximize total points.
• Avoid Heavy Prefix Sums: While prefix sum arrays work, managing dynamic variables is cleaner, easier to explain, and avoids unnecessary boilerplate.
• Initial State Assumption: Always start by assuming all $K$ elements are picked from the front (leftSum).
• Sliding Window Mechanics: In each iteration of the backward loop (K-1 down to 0), drop one element from the left sum and append the next available element from the right back index.
• Global Maximum Tracking: Compare leftSum + rightSum against a running maxSum variable at every single step.
• Optimal Efficiency: Achieves an optimal $\mathcal{O}(K)$ time complexity and $\mathcal{O}(1)$ auxiliary space complexity.