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.
This approach uses a max-heap (priority queue) to efficiently track and operate on the largest element. The primary idea is to reverse the operation: starting from the target array, every large element in the target can be seen as the result of adding all smaller elements in the array to one of the array's elements during the last operation. By repeatedly transforming the largest element in this manner, we can verify if it is possible to reach the initial array of ones.
This C solution utilizes a sorting approach to repeatedly operate on the largest element in the array. Given the target array, it first computes the sum of the array and sorts it to keep track of the largest element. The largest element is reduced by subtracting the rest of the sum in a manner that the new largest element would be a remainder from division by rest of the array sum, thus reversing the process of the original operation. This is continued until either the array is reduced to all ones or an impossible state is reached.
The time complexity is O(n log n * log maxValue) due to sorting and heap operations, where n is the number of elements and maxValue is the maximum integer in the target. The space complexity is O(1) since we are sorting and using in-place operations optimistically.
This approach utilizes a sort and modulo method to reverse-track the process involved in constructing the target array from an array containing ones. It revolves around repeatedly reducing the maximum value to the remainder after division with the sum of other elements.
Steps include:
In this solution, once again a sorting technique is employed to control the biggest element in the target array for each operation. This allows management of the leading maximal element's transformation. By reducing the main element while checking the constraints, the algorithm either resolves the target to all ones or determines impossibility.
Time complexity is O(n log n * log maxValue); space complexity is O(1) when using in-place operations for sorting and arithmetic.
We observe that if we start constructing the target array target from the array arr in a forward manner, it is difficult to determine which index i to choose each time, making the problem quite complex. However, if we construct in reverse starting from the array target, each construction step must select the largest element in the current array, which ensures that each construction is unique, making the problem relatively simple.
Therefore, we can use a priority queue (max heap) to store the elements of array target, and use a variable s to record the sum of all elements in array target. Each time we extract the maximum element mx from the priority queue and calculate the sum t of all elements in the current array except mx. If t \lt 1 or mx - t \lt 1, it means the target array target cannot be constructed, and we return false. Otherwise, we calculate mx bmod t. If mx bmod t = 0, we set x = t; otherwise, we set x = mx bmod t. We add x to the priority queue and update the value of s. We repeat this process until all elements in the priority queue become 1, at which point we return true.
The time complexity is O(n log n) and the space complexity is O(n), where n is the length of array target.
| Approach | Complexity |
|---|---|
| Approach 1: Max-Heap Backtracking | The time complexity is O(n log n * log maxValue) due to sorting and heap operations, where n is the number of elements and maxValue is the maximum integer in the target. The space complexity is O(1) since we are sorting and using in-place operations optimistically. |
| Approach 2: Iterative Modulo with Sorting | Time complexity is O(n log n * log maxValue); space complexity is O(1) when using in-place operations for sorting and arithmetic. |
| Reverse Construction + Priority Queue (Max Heap) | — |
| 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 |
Construct Target Array With Multiple Sums || Leetcode • Pepcoding • 6,121 views views
Watch 9 more video solutions →Practice Construct Target Array With Multiple Sums with our built-in code editor and test cases.
Practice on FleetCode