Skip to main content

1686. Stone Game VI

medium

Alice and Bob each have their own value for every stone; both want to maximize their own total. The optimal strategy is greedy on the SUM of the two players' valuations — a famous case where game-DP collapses to sorting.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Alice and Bob take turns playing a game, with Alice starting first. There are n stones in a pile. On each player's turn, they can remove a stone from the pile and receive points based on the stone's value. Alice and Bob may value the stones differently. You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the ith stone. The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally. Both players know the other's values. Determine the result of the game, and: If Alice wins, return 1. If Bob wins, return -1. If the game results in a draw, return 0.

Constraints

  • n == aliceValues.length == bobValues.length
  • 1 <= n <= 10^5
  • 1 <= aliceValues[i], bobValues[i] <= 100

Examples

Example 1

Input
aliceValues = [1,3], bobValues = [2,1]
Output
1

Explanation: If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points. Bob can only choose stone 0, and will get 2 points. Alice wins.

Example 2

Input
aliceValues = [1,2], bobValues = [3,1]
Output
0

Explanation: If Alice takes stone 0, Alice will receive 1 point. Bob will choose stone 1, and will get 1 point. Tie.

Example 3

Input
aliceValues = [2,4,3], bobValues = [1,6,7]
Output
-1

Explanation: Regardless of what Alice does, Bob will be able to have more points than Alice. For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Each turn the mover effectively swings the score difference by (their value) + (opponent's foregone value).

Hint 2

Sort stones by (aliceValues[i] + bobValues[i]) descending. Alice picks the 0th, 2nd, 4th, ... stones; Bob the 1st, 3rd, ... ones.

Hint 3

Tally each player's points using their own valuation. Compare totals at the end.

Hint 4

Listed in dp-2d for the game-DP family — the optimal solution is greedy, not a 2D table, but it sits in the Stone Game series.

Solution approach

Reveal approach

Greedy on combined value, with a game-theory justification. For each stone i, both players care about removing it because removing it gives the mover aliceValues[i] (or bobValues[i]) AND denies the opponent bobValues[i] (or aliceValues[i]). The net swing of taking stone i for the mover is aliceValues[i] + bobValues[i] (or bobValues[i] + aliceValues[i] for Bob). So both players prefer to grab the stone with the largest combined value. Build pairs (aliceValues[i] + bobValues[i], i), sort descending by sum. Alice takes the even-indexed pairs after sorting, Bob the odd-indexed. Tally Alice's score with aliceValues and Bob's with bobValues. Return sign of the difference. O(n log n). Listed in dp-2d for the game-DP family.

Complexity

Time
O(n log n)
Space
O(n)

Related patterns

  • greedy
  • game-theory
  • sorting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Stone Game VI and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →