Watch 10 video solutions for Construct Target Array With Multiple Sums, a hard level problem involving Array, Heap (Priority Queue). This walkthrough by Pepcoding has 6,121 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 :
x be the sum of all elements currently in your array.i, such that 0 <= i < n and set the value of arr at index i to x.Return true if it is possible to construct the target array from arr, otherwise, return false.
Example 1:
Input: target = [9,3,5] Output: true Explanation: Start with arr = [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 <= n <= 5 * 1041 <= target[i] <= 109Problem Overview: You start with an array of n ones. In one operation, choose an index and replace its value with the sum of the entire array. Given a target array, determine whether it could have been constructed after several such operations. The challenge is that values grow very quickly, so simulating forward from all ones is infeasible.
Approach 1: Max-Heap Backtracking (O(n log n) time, O(n) space)
Work backwards instead of forwards. The largest value in the array must be the element that was updated in the most recent operation. If the total sum is S and the largest element is max, then before the last step that element must have been max - (S - max). Maintain the numbers in a heap (priority queue) so you can repeatedly extract the largest element in O(log n). Each iteration removes the max element, computes the previous value using the remaining sum, and pushes it back. Invalid states occur when the remaining sum becomes zero or the computed value is not positive. Continue until every element becomes 1. This greedy reverse simulation keeps the largest value under control and avoids exponential growth.
Approach 2: Iterative Modulo with Sorting (O(k * n log n) time, O(1) extra space)
The same reverse insight can be implemented without a heap. Sort the array to identify the largest value each iteration, compute the remaining sum, and reduce the largest element using modulo: prev = max % rest. This step compresses multiple reverse operations at once, which prevents extremely large loops when the maximum dominates the array. After updating the element, reinsert it and sort again to find the next maximum. While the logic is straightforward and relies only on array manipulation, repeated sorting makes it slower than the heap-based solution.
The key observation behind both approaches is greedy reversal: the current largest value must have been created by adding the sum of all other elements. Using modulo effectively skips many repeated subtractions when values are huge.
Recommended for interviews: The Max-Heap Backtracking approach. Interviewers expect candidates to recognize the reverse greedy strategy and manage the largest element efficiently with a priority queue. Explaining why the largest value must be processed first demonstrates strong reasoning about array sums and greedy reconstruction.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Max-Heap Backtracking | O(n log n) | O(n) | Best general solution; efficiently tracks the largest element using a priority queue |
| Iterative Modulo with Sorting | O(k * n log n) | O(1) | Useful when avoiding extra data structures, but slower due to repeated sorting |