Maximum Points from Cards - Sliding Window - Visualization - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

You are given an integer array cardPoints and an integer k. In one move, you can take one card from the beginning or the end of the array. Your task is to return the maximum score you can obtain by choosing exactly k cards.

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: Pick the cards [1, 6, 5] or [6, 5, 1], total = 12.

Examples❯

cardPoints k Output Description
[1,2,3,4,5,6,1] 3 12 Pick last 2 cards [6,1] and first card [5] for a total of 12
[2,2,2] 2 4 Take any two cards; all have value 2
[9,7,7,9,7,7,9] 7 55 Take all cards since k = length; sum of all = 55
[1,1000,1] 1 1 Best of first or last; both are 1
[1,1000,1] 2 1001 Choose 1000 and 1 from either end
[1,79,80,1,1,1,200,1] 3 202 Choose [1,200,1] from end or best 3 combination totaling 202
[100,40,17,9,73,75] 3 248 Pick [100,40,108] from beginning or mix ends for max sum
[1,2,3,4,5] 0 0 Choose 0 cards; total score is 0
[] 0 0 Empty card list; score is 0 regardless of k
[] 2 0 Empty card list; cannot take any cards even if k>0

Solution❯

Understanding the Problem

We are given an array called cardPoints, and an integer k. Imagine you are playing a game where you can pick exactly k cards, but only from the start or end of the array—never from the middle.

Your goal is to get the maximum possible score by picking k cards in total, from either end. The score is simply the sum of the selected cards.

For example, given:

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

You can choose the cards [1, 6, 5] (from end and start), and their sum is 12. This is the highest possible score with 3 cards.

Step-by-Step Solution with Example

Step 1: Understand the Brute Force Approach

If we try every combination of k cards from the front and back, the number of possibilities is large. For example:

  • Take all 3 cards from the front: [1, 2, 3]
  • Take 2 from front and 1 from back: [1, 2, 1]
  • Take 1 from front and 2 from back: [1, 6, 1]
  • Take all 3 from the back: [6, 1, 5]

We can’t afford to try all combinations for large arrays. So we need an efficient method.

Step 2: Use Sliding Window Intuition

Here’s the key trick: instead of choosing which k cards to take, we can think of which n-k cards to leave out in the middle. Why?

Because you’re only allowed to pick cards from the two ends. So the cards you don’t pick are a continuous segment in the middle of the array.

Step 3: Calculate Total Sum and Find Minimum Middle Window

We first calculate the total sum of all the cards — this is the score if we could pick all cards.

Then, we find the minimum sum of any subarray of length n - k (i.e., the unpicked cards). We subtract this from the total to get the maximum score.


cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
Total cards = 7
We need to skip a window of 7 - 3 = 4 cards.

Try all subarrays of length 4:
[1, 2, 3, 4] → sum = 10  
[2, 3, 4, 5] → sum = 14  
[3, 4, 5, 6] → sum = 18  
[4, 5, 6, 1] → sum = 16  

Minimum sum = 10 (skip these 4 cards)
Total sum = 1+2+3+4+5+6+1 = 22  
Max score = 22 - 10 = 12

Step 4: Code It with Sliding Window

We can use a sliding window of size n - k to compute this efficiently without checking all subarrays manually.

Edge Cases

  • k = cardPoints.length: You take all the cards, return the total sum.
  • k = 0: You take no cards, score is 0.
  • All elements are equal: Any selection of k cards will result in the same total score.
  • Large values at both ends: Choosing from both ends should be considered (e.g., [1000, 1, 1, 1, 1000]).

Final Thoughts

This is a classic example of converting a selection problem into a window-based optimization. Instead of brute-force checking all combinations of taking cards from both ends, we slide a window over the part we skip and subtract it from the total. This makes the solution efficient and elegant.

Sliding window techniques are powerful when the problem involves contiguous subarrays or a fixed number of operations across a range. Always look for ways to turn the problem "inside out" like we did here.

Algorithm Steps❯

  1. Calculate the total sum of the last k cards and store it as the initial maxScore.
  2. Use a sliding window of size k, where you move the window from the end of the array towards the start.
  3. In each step, remove one card from the end of the current window and add one card from the front of the array.
  4. Track the updated sum after each step and update maxScore accordingly.
  5. Repeat this process k times to check all combinations of cards taken from front and back.
  6. Return maxScore as the result.

Code

Python
Java
JS
C
C++
Go
Rust
Kotlin
Swift
TS
from typing import List

def max_points_from_cards(cardPoints: List[int], k: int) -> int:
    n = len(cardPoints)
    current_sum = sum(cardPoints[n - k:])
    max_score = current_sum
    for i in range(k):
        current_sum += cardPoints[i] - cardPoints[n - k + i]
        if current_sum > max_score:
            max_score = current_sum
    return max_score

# Example usage
card_points = [1, 2, 3, 4, 5, 6, 1]
k = 3
print(max_points_from_cards(card_points, k))  # Output: 12

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(k)To calculate the initial sum of the last k cards and then slide the window k times, each involving a constant number of operations. Even in the best case, all k moves must be considered to find the maximum score.
Average CaseO(k)The algorithm checks all combinations by shifting a window of size k from the back to the front. This involves k+1 total iterations with constant-time operations, resulting in linear complexity with respect to k.
Worst CaseO(k)The sliding window is moved k times to cover all combinations of front and back picks. Each step involves only basic arithmetic, so the total time complexity is O(k).

Space Complexity❯

O(1)

Explanation: Only a fixed number of variables are used to maintain the current score, max score, and intermediate sums. No additional data structures are used regardless of the input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...