Construct Target Array With Multiple Sums

Problem Id: 1354 Difficulty: Hard Tag: Greedy


Intuition

First, the order of the target makes no difference whether if could be got from the method given. So we could change the order of the target list.

Another thing is that, since all numbers are negative, the biggest element in the target is always the last one. And we could easily get the list before last change by minus the biggest element with the sum of all left elements.

So we could solve it by Greedy. Every time we move one step up by changing the biggest element.

Since we should always handle with the biggest element, we could use a heap (priority queue) to store the list so that we could always get the biggest one in time O(lgn).

Solution


import heapq


class Solution:
    def isPossible(self, target: List[int]) -> bool:
        nums = []
        for num in target:
            heapq.heappush(nums, -num)
        total = sum(target)

        while True:
            elem = -heapq.heappop(nums)
            if elem == 1:
                return True
            left = total - elem
            prev = elem - left
            if prev < 0:
                return False
            heapq.heappush(nums, -prev)
            total -= elem - prev