LC-1686 Medium LeetCode

1686. Stone Game VI

Array Math Greedy Sorting Heap (Priority Queue) Game Theory

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 59% Topics: Array, Math, Greedy, Sorting, Heap (Priority Queue), Game Theory

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

class Solution(object):
    def stoneGameVI(self, aliceValues, bobValues):
        """
        :type aliceValues: List[int]
        :type bobValues: List[int]
        :rtype: int
        """
        sorted_vals = sorted(((a, b) for a, b in zip(aliceValues, bobValues)), key=sum, reverse=True)
        return cmp(sum(a for a, _ in sorted_vals[::2]), sum(b for _, b in sorted_vals[1::2]))

Solution from kamyu104/LeetCode-Solutions · MIT