Construct Target Array With Multiple Sums — LeetCode 1354 Python Solution

The problem

You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure : let x be the sum of all elements currently in your array.

Example

Input

target = [9,3,5]

Output

true

Explanation

Start with arr = [1, 1, 1]

Python solution

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        s = sum(target)
        pq = [-x for x in target]
        heapify(pq)
        while -pq[0] > 1:
            mx = -heappop(pq)
            t = s - mx
            if t == 0 or mx - t < 1:
                return False
            x = (mx % t) or t
            heappush(pq, -x)
            s = s - mx + x
        return True

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1354. Construct Target Array With Multiple Sums is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

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

Related problems