0542MediumArraySliding WindowPrefix Sum

Forklift Picks from the Crate Row

Tracked in this browser only

Trains the technique from

LeetCode 1423Maximum Points You Can Obtain from Cards

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Crates stand in a single line along a loading aisle. cardPoints[i] is the mass of the crate at position i, reading from the front of the line to the back.

A forklift makes exactly k pickups. Each pickup removes either the crate currently at the front of the line or the crate currently at the back of the line; the crate behind or in front of it then becomes the new end. Nothing may be taken from the middle.

Return the largest total mass the forklift can carry away.

Examples

Example 1

Input: cardPoints = [5, 4, 9, 1], k = 2
Output: 10

Take the back crate of mass 1, then the crate of mass 9 that is now at the back. Both pickups came from an end and there were exactly two of them, giving 10.

Example 2

Input: cardPoints = [6, 6, 6], k = 2
Output: 12

Every crate weighs 6, so any two pickups carry away 12.

Example 3

Input: cardPoints = [7, 4, 8], k = 3
Output: 19

There are three crates and three pickups, so the line empties and the whole 7 + 4 + 8 = 19 leaves on the forklift.

Constraints

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_score(cardPoints: list[int], k: int) -> int:

Java

public int maxScore(int[] cardPoints, int k)

The intended approach

Time O(n): one pass to total the line and one pass for the sliding window.Space O(1) beyond the input list.

Whatever order the pickups happen in, the crates still standing at the end are always one unbroken block of `n - k` consecutive crates, because removals only ever eat inward from the two ends. So the mass carried away equals the mass of the whole line minus the mass of that block, and the largest haul comes from the lightest block of length `n - k`. Total the line, then slide a window of that length across it once, adding the entering crate and subtracting the leaving crate, and keep the smallest window total. When `k` equals the line length the block is empty and the whole line is taken.

Pythonentry point: max_score

def max_score(cardPoints, k):
    # O(n) time, O(1) extra space. Whatever the forklift takes, the crates left
    # standing form one block of exactly n - k consecutive crates, so the mass
    # taken is the whole row minus that block. Slide a window of that length
    # once and keep the lightest block seen.
    n = len(cardPoints)
    whole = 0
    for v in cardPoints:
        whole += v
    left = n - k
    if left == 0:
        return whole
    window = 0
    for i in range(left):
        window += cardPoints[i]
    lightest = window
    for i in range(left, n):
        window += cardPoints[i] - cardPoints[i - left]
        if window < lightest:
            lightest = window
    return whole - lightest

The obvious version

Every pickup sequence is described by how many crates came off the front, which is some number from 0 to k with the rest coming off the back. Try each split, add up that many crates from the front and the remainder from the back, and keep the largest total.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_score(cardPoints, k):
    n = len(cardPoints)
    best = None
    for front in range(k + 1):
        back = k - front
        total = 0
        for i in range(front):
            total += cardPoints[i]
        for i in range(back):
            total += cardPoints[n - 1 - i]
        if best is None or total > best:
            best = total
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in