The O(n) Club: Maximum Points You Can Obtain from Cards — Sliding Windows, Not Heart Attacks

⚡ TL;DR

Grab k cards from either the start or end of an array. Don’t brute force every combo like you hate yourself. Slide a window over possible end-start splits and stay sane. Here’s a Java brute force nobody should really use:

🧠 How Devs Usually Mess This Up

You see “pick k from either end” and suddenly there’s recursion everywhere and a combinatorial explosion the size of 2020. Here’s how devs go wrong:

🔍 What’s Actually Going On

Imagine a sandwich you can eat only from either end but you have to take exactly k bites. All legal “meals” are some from the left, some from the right — every possible split, from all right to all left. Instead of brute-force food poisoning, you:

🛠️ PseudoCode

For each card from 1 to k: add one from the left, remove one from the right.
Update max as you go.

Return max.

Slide window leftwards:

for (int i = 0; i < k; i++) {
    total += cards[i] - cards[cards.length - k + i];
    max = Math.max(max, total);
}

You’re mixing left and right, like you’re DJing a playlist for maximal points.

Sum the last k cards (all right-side picks):

int total = 0;
for (int i = cards.length - k; i < cards.length; i++) total += cards[i];
int max = total;

You’re pretending you took all your picks from the right.

💻 The Code

public int maxScore(int[] cardPoints, int k) {
    int n = cardPoints.length;
    int total = 0;
    for (int i = n - k; i < n; i++) total += cardPoints[i];
    int max = total;
    for (int i = 0; i < k; i++) {
        total += cardPoints[i] - cardPoints[n - k + i];
        max = Math.max(max, total);
    }
    return max;
}

⚠️ Pitfalls, Traps & Runtime Smacks

k == array length: Don’t overthink. Just sum everything and go home early.
Zero or negative card values: Still totally fine. Only your optimism will be negative, not your code.
Random subset delusion: Only ends matter. If you’re trying anything fancier for this, take a coffee break.
Speed/Memory: Time: O(k). Space: O(1). Interviewers love to see you use less RAM than a 1998 pager.

🧠 Interviewer Brain-Tattoo

“When the problem says ‘pick k from either end,’ just slide that window. Or prepare for a recursion hangover.”

The O(n) Club Array Sliding Window Prefix Sum

The O(n) Club: Maximum Points You Can Obtain from Cards — Sliding Windows, Not Heart Attacks