Show problems as
Classic problem #877MediumArrayMathDynamic ProgrammingMinimaxGame TheoryZero-Sum Game

Stone Game

Real-world version: Shelf End Bidding Duel
Tracked in this browser only
Read Stone Game on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A closing auction lines up piles sealed bins on a shelf, left to right. Bin i contains piles[i] tokens.

Iris claims a bin first, then Odell, and they keep alternating. A claim always takes one whole bin from either the far left or the far right of whatever is still on the shelf, and every token inside a claimed bin is credited to whoever claimed it. The duel ends when the shelf is bare, and by then every bin has been claimed.

Each of them plays for the largest personal token total they can force, whatever the other one does.

Return true if Iris finishes with a strictly larger token total than Odell, and false otherwise.

Examples

Example 1

Input
piles = [3, 9, 1, 2]
Output
true

Iris ends the duel with a strictly larger token total than Odell, so true is returned.

Example 2

Input
piles = [1, 2]
Output
true

Iris claims the right-hand bin for 2 tokens, Odell is left with the bin holding 1, and 2 beats 1.

Example 3

Input
piles = [5, 4, 3, 1]
Output
true

Iris finishes ahead of Odell over the four claims.

Example 4

Input
piles = [2, 7, 4, 8, 9, 1]
Output
true

Iris finishes with a larger total than Odell across the six claims, so true is returned.

Constraints

  • 2 <= piles.length <= 500
  • piles.length is even.
  • 1 <= piles[i] <= 500
  • sum(piles[i]) is odd.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def first_bidder_wins(bins: list[int]) -> bool:
Java
public boolean firstBidderWins(int[] bins)

More on the same topics