Problem 1423

Abstract / Summary

Choose cards to maximize points by picking every third card or skipping one to take the next.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1423.py

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # take only cards from the left side
        result = sum(cardPoints[:k])
        left   = k - 1
        right  = len(cardPoints) - 1
        have   = result
        while left >= 0:
            have  -= cardPoints[left]
            have  += cardPoints[right]
            result = max(result, have)

            left  -= 1
            right -= 1

        return result
16 lines | 471 bytes | submitted November 13, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 57% (800k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Prefix Sum
  • Sliding Window
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the maximum possible sum of k cards that can be taken from either end of a list of integers. It does this by first assuming all selected cards come from the left side, then progressively replaces left-most cards with right-most cards while tracking the best total encountered.

Initial Accumulation

result = sum(cardPoints[:k])

The algorithm begins by summing the first k elements of the input list. This represents the scenario where every chosen card is taken from the left end. The variable result holds the best score found so far.

Sliding Window Setup

left   = k - 1
right  = len(cardPoints) - 1
have   = result

Three pointers are prepared:

  • left points to the index of the last card that was included from the left side.
  • right points to the last element of the list, the candidate to be taken from the right side.
  • have mirrors the current sum of the selected k cards, allowing the algorithm to adjust the total without recomputing it from scratch.

Iterative Replacement

while left >= 0:
    have  -= cardPoints[left]
    have  += cardPoints[right]
    result = max(result, have)

    left  -= 1
    right -= 1

During each loop iteration the algorithm:

  1. Removes the value at left from the current sum (have).
  2. Adds the value at right to have, effectively swapping one left-side card for a right-side card.
  3. Updates result if the new sum exceeds the previous best.

Both pointers are then moved one step toward the start of the list, preparing for the next possible swap. The loop continues until every left-side card has been considered for replacement, guaranteeing that all combinations of taking i cards from the left and k-i cards from the right are examined.

Return Value

return result

After the loop finishes, result contains the maximum achievable sum for any valid selection of k cards from the two ends, and this value is returned to the caller.

Edge Cases Handled

When k equals the length of cardPoints, the initial sum already includes every element. The loop still executes, but each iteration subtracts and adds the same element, leaving the total unchanged. Consequently, the algorithm correctly returns the sum of the entire list.

If k is zero, the slice cardPoints[:0] yields an empty list, and sum returns 0. The loop condition left >= 0 fails immediately because left is initialized to -1. The function therefore returns 0, which is the appropriate result for taking no cards.

When the list contains a single element and k is 1, the initial sum captures that element. The loop runs once, swapping the same element with itself, and the final result remains the original value, satisfying the requirement.

Performance Optimizations

The core optimization lies in the sliding-window technique. By maintaining a running total (have) and adjusting it with a constant-time subtraction and addition for each shift, the algorithm avoids recomputing the sum of k elements on every iteration. This yields linear execution time relative to the length of the input list while using only a handful of scalar variables, resulting in constant auxiliary space. The use of direct indexing (cardPoints[left] and cardPoints[right]) ensures that each element is accessed exactly once during the sliding process.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a row of colorful cards laid out on a table, and each card has a different number written on it. This code is like a game where the goal is to pick up exactly a certain number of cards, but you are only allowed to grab them from the very edges of the row.

At the start, the computer pretends to pick up all the required cards from the far left side. It adds up their values to see what the total score is.

Then, the computer imagines sliding its hand slightly to the right. It puts one card back from the left side and picks up a new card from the very end of the right side instead. It checks if this new combination of cards makes a bigger total score than before.

It keeps doing this, shuffling cards in from the right while putting ones back on the left, until it has checked every possible way to pick up that specific number of cards from the edges. Throughout the whole game, it remembers the highest score it has seen so far so it can show the best possible outcome at the end.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.70 | σ = 0.76

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java JS Go C# Dart PHP Ruby Rust Scala Swift TS
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
MacJim C++
trung-hn Python
varunu28 Java
vthwang Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Dart, Go, Java, JavaScript, PHP, Python, Ruby, Rust, Scala, Swift, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
MacJim C++
trung-hn Python
varunu28 Java
vthwang Java
YuriSpiridonov Python
37 links | 18 authors | 13 languages

Videos

9 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

10 solutions   November 13, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality