DEV Community

loading...
Cover image for Solution: Construct Target Array With Multiple Sums

Solution: Construct Target Array With Multiple Sums

seanpgallivan profile image seanpgallivan ・5 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #1354 (Hard): Construct Target Array With Multiple Sums


Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given an array of integers target. From a starting array, A consisting of all 1's, you may perform the following procedure :

  • let x be the sum of all elements currently in your array.
  • choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
  • You may repeat this procedure as many times as needed.

Return True if it is possible to construct the target array from A otherwise return False.


Examples:

Example 1:
Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1]
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done
Example 2:
Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].
Example 3:
Input: target = [8,5]
Output: true

Constraints:

  • N == target.length
  • 1 <= target.length <= 5 * 10^4
  • 1 <= target[i] <= 10^9

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

One thing we can notice right away: The sum of the elements in A will always be larger than any single element of A, since A starts off with all positive numbers. Therefore, the sum will only ever go up as we iterate through the solution process. This means that we will only ever have one attempt to place a given number in its correct spot.

It also means that the last step will always be to settle the highest value of the target array, which means we can reconstruct the nature of A right before the last step as well. From there, we'll have to keep dealing with the largest remaining value, on and on, working backwards until we either succeed or fail.

Since we are going to have to deal with the target values in descending value order, it stands to reason that we should use a max priority queue or max-heap structure to keep track of the target values, especially since we don't care about the values' indices.

Once we have all the target values inserted into the priority queue (pq/heap) and the sum calculated, we can proceed to deal with the values in order. At each step, we should remove the max value, compute its replacement's value, then reinsert that replacement back into pq. If, at the start of an iteration, we see that the max value in pq is a 1, then that means that all values in pq are 1s, and we should return true.

On the other hand, if we find ourselves about to insert a number less than 1 into pq, we know we've failed and should return false, as we will have passed the prescribed starting position.

But at this point, we'll still obtain a TLE result and will need to optimize some more. Consider the situation in which we process the max value only to find that we're about to reinsert a number that is still the max value. In some edge cases, it could take thousands of iterations to fully process this value so that we can move on to another, when all that processing can be done more simply in one step.

Take, for example, target = [3,5,33]. Normally, we'd remove the 33 and compute its replacement to be 25, then from 25 to 17, then 17 to 9, then finally 9 to 1. Each time, we're removing the sum of all the remaining values (3 + 5 = 8) from the current number. In any valid target array, as we noted at the very beginning, the max value must be larger than the sum of the remaining elements, since it came from that sum plus the value that was replaced.

That means that we should be able to remove the remaining sum (8) from our current max value (33) as many times as we possibly can, since only the remainder will bring us below that sum. This we can achieve quite easily with the mod operator which will result in our replacement value (33 % 8 = 1) without the need to iterate through every step.

As noted recently, if we find that the max value is actually less than the remaining sum, then the array must not be valid, and we can return false. Also, if num should end up being 0 after applying the mod operator, then we should return false, except for the edge case where sum = 1. Alternately, we could instead push sum onto pq intead of num, which will immediately trigger a failure in all but the edge case.


Implementation:

Javascript's MaxPriorityQueue() npm is convenient, but not terribly efficient. A custom max-heap implementation is more performant. Both options are included below.

Python defaults to a min-heap, so we can simulate a max-heap by changing the sign on each element when it is inserted and removed from the heap.


Javascript Code:


(Jump to: Problem Description || Solution Idea)

w/ MaxPriorityQueue():
var isPossible = function(target) {
    let pq = new MaxPriorityQueue({priority: x => x}), sum = 0
    for (let num of target) sum += num, pq.enqueue(num)
    while (pq.front().element !== 1) {
        let num = pq.dequeue().element
        sum -= num
        if (num <= sum || sum < 1) return false
        num %= sum, sum += num, pq.enqueue(num || sum)
    }
    return true
};
Enter fullscreen mode Exit fullscreen mode
w/ Max-Heap:
var isPossible = function(target) {
    let heap = [,], sum = 0

    const heapify = val => {
        let i = heap.length, par = i >> 1, temp
        heap.push(val)
        while (heap[par] < heap[i]) {
            temp = heap[par], heap[par] = heap[i], heap[i] = temp
            i = par, par = i >> 1
        }
    }
    const extract = () => {
        if (heap.length === 1) return null
        let top = heap[1], left, right, temp,
            i = 1, child = heap[3] > heap[2] ? 3 : 2
        if (heap.length > 2) heap[1] = heap.pop()
        else heap.pop()
        while (heap[i] < heap[child]) {
            temp = heap[child], heap[child] = heap[i], heap[i] = temp
            i = child, left = i << 1, right = left + 1
            child = heap[right] > heap[left] ? right : left
        }
        return top
    }

    for (let num of target) sum += num, heapify(num)
    while (heap[1] !== 1) {
        let num = extract()
        sum -= num
        if (num <= sum || sum < 1) return false
        num %= sum, sum += num, heapify(num || sum)
    }
    return true
};
Enter fullscreen mode Exit fullscreen mode

Python Code:


(Jump to: Problem Description || Solution Idea)

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        heap = [-num for num in target]
        total = sum(target)
        heapify(heap)
        while heap[0] != -1:
            num = -heappop(heap)
            total -= num
            if num <= total or total < 1: return False
            num %= total
            total += num
            heappush(heap, -num or -total)
        return True
Enter fullscreen mode Exit fullscreen mode

Java Code:


(Jump to: Problem Description || Solution Idea)

class Solution {
    public boolean isPossible(int[] target) {
        Queue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
        int sum = 0;
        for (int num : target) {
            sum += num;
            pq.add(num);
        }
        while (pq.peek() != 1) {
            int num = pq.poll();
            sum -= num;
            if (num <= sum || sum < 1) return false;
            num %= sum;
            sum += num;
            pq.add(num > 0 ? num : sum);
        }
        return true;
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:


(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<int> pq;
        unsigned int sum = 0;
        for (int num : target)
            sum += num, pq.push(num);
        while (pq.top() != 1) {
            int num = pq.top();
            pq.pop();
            sum -= num;
            if (num <= sum || sum < 1) return false;
            num %= sum, sum += num, pq.push(num ? num : sum);
        }
        return true;
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (3)

Collapse
crownedprinz profile image
Ademola John

Impressive. Cool explanation

Collapse
seanpgallivan profile image
Collapse
seanpgallivan profile image
seanpgallivan Author

Corrected an issue with a missing failure condition! The last paragraph of the Idea section has been updated, as well as the respective code.

Forem Open with the Forem app