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

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:

// Don't ever actually run this in production
int maxScore(int[] cards, int k) {
    return maxScoreHelper(cards, 0, cards.length - 1, k);
}
int maxScoreHelper(int[] cards, int l, int r, int k) {
    if (k == 0) return 0;
    return Math.max(cards[l] + maxScoreHelper(cards, l+1, r, k-1),
                    cards[r] + maxScoreHelper(cards, l, r-1, k-1));
}
// Close tab before your laptop starts crying

🧠 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

• 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.
• Slide window leftwards:
  
  • For each card from 1 to k: add one from the left, remove one from the right.
  • Update max as you go.

  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.
• Return max.

💻 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.”