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
Difficulty
and has an acceptance rate of about 57% (800k+ submissions).
Typical patterns to solve this problem:
- Array
- Prefix Sum
- Sliding Window
AI Disclaimer
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.
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:
leftpoints to the index of the last card that was included from the left side.rightpoints to the last element of the list, the candidate to be taken from the right side.havemirrors the current sum of the selectedkcards, 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:
- Removes the value at
leftfrom the current sum (have). - Adds the value at
righttohave, effectively swapping one left-side card for a right-side card. - Updates
resultif 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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 2379: Minimum Recolors to Get K Consecutive Black Blocks
Solved On The Same Day
- problem 1436: Destination City
- problem 1446: Consecutive Characters
- problem 1450: Number of Students Doing Homework at a Given Time
- problem 1432: Max Difference You Can Get From Changing an Integer
- problem 1433: Check If a String Can Break Another String
- problem 1447: Simplified Fractions
- problem 1451: Rearrange Words in a Sentence
- problem 1452: People Whose List of Favorite Companies Is Not a Subset of Another List
- problem 1483: Kth Ancestor of a Tree Node
Extra
- 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