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,Aconsisting of all1's, you may perform the following procedure :
- let
xbe the sum of all elements currently in your array.- choose index
i, such that0 <= i < target.sizeand set the value ofAat indexitox.- You may repeat this procedure as many times as needed.
Return
Trueif it is possible to construct thetargetarray fromAotherwise returnFalse.
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.length1 <= target.length <= 5 * 10^41 <= 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
};
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
};
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
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;
}
}
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;
}
};
Top comments (3)
Impressive. Cool explanation
Thanks!
Corrected an issue with a missing failure condition! The last paragraph of the Idea section has been updated, as well as the respective code.