How hard is LeetCode 1686. Stone Game VI?

LeetCode 1686. Stone Game VI is rated Medium on LeetCode.

What is the time complexity of LeetCode 1686. Stone Game VI?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1686. Stone Game VI?

The Python solution on this page uses O(n), where n is the length of the arrays `aliceValues` and `bobValues` auxiliary space.

What topics does LeetCode 1686. Stone Game VI cover?

LeetCode 1686. Stone Game VI is tagged Greedy, Array, Math, Game Theory, Sorting and Heap (Priority Queue) on LeetCode.

Stone Game VI — LeetCode 1686 Python Solution

MediumGreedyArrayMathGame TheorySortingHeap (Priority Queue)

Problem: #1686
Pattern: Heap / Priority Queue
Reading time: 2 min
Source: leetcode.com

The problem

Alice and Bob take turns playing a game, with Alice starting first. There are n stones in a pile.

Example

Input: aliceValues = [1,3], bobValues = [2,1]
Output: 1
Explanation: If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points.

Python solution

Python

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        vals = [(a + b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))]
        vals.sort(reverse=True)
        a = sum(aliceValues[i] for _, i in vals[::2])
        b = sum(bobValues[i] for _, i in vals[1::2])
        if a > b:
            return 1
        if a < b:
            return -1
        return 0

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n), where n is the length of the arrays `aliceValues` and `bobValues` auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1686. Stone Game VI is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1686. Stone Game VI?: LeetCode 1686. Stone Game VI is rated Medium on LeetCode.
What is the time complexity of LeetCode 1686. Stone Game VI?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1686. Stone Game VI?: The Python solution on this page uses O(n), where n is the length of the arrays `aliceValues` and `bobValues` auxiliary space.
What topics does LeetCode 1686. Stone Game VI cover?: LeetCode 1686. Stone Game VI is tagged Greedy, Array, Math, Game Theory, Sorting and Heap (Priority Queue) on LeetCode.