Skip to main content
Talentd

Construct Target Array With Multiple Sums - Solution & Explanation

HardArrayHeap (Priority Queue)26 min readAsked at: Quora
Practice this problem

Problem Statement

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 :

  • let x be the sum of all elements currently in your array.
  • choose index i, such that 0 <= i < n and set the value of arr 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 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.length
  • 1 <= n <= 5 * 104
  • 1 <= target[i] <= 109

Approach Overview

Problem 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 1: Approach 1: Max-Heap Backtracking

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.

  1. Create a max-heap and compute the total sum of the target array.
  2. Iteratively replace the largest element max with max % rest, where rest is the sum of all elements except max.
  3. Continue this process until all elements are ones or it's impossible to proceed.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Iterative Modulo with Sorting

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:

  1. Sort the target array descending and compute the total sum.
  2. Continue to find the largest element and replace it by modding it with the rest of the sum, adjusting the total sum.
  3. Return the possibility of the transformation when all elements are reduced to one, or halt if impossible.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n log n * log maxValue); space complexity is O(1) when using in-place operations for sorting and arithmetic.

Try this approach in the editor →

Approach 3: Reverse Construction + Priority Queue (Max Heap)

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Max-Heap BacktrackingO(n log n)O(n)Best general solution; efficiently tracks the largest element using a priority queue
Iterative Modulo with SortingO(k * n log n)O(1)Useful when avoiding extra data structures, but slower due to repeated sorting

Video Solution

Construct Target Array With Multiple Sums || Leetcode • Pepcoding • 6,239 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Construct Target Array With Multiple Sums easy or hard?
Construct Target Array With Multiple Sums is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the reverse greedy strategy and applying modulo optimization to avoid extremely slow repeated subtraction.
Construct Target Array With Multiple Sums Python/Java solution
Python and Java implementations typically use a priority queue (heapq in Python with negated values, or PriorityQueue in Java). Each iteration pops the largest number, computes the previous value using the remaining sum and modulo, then pushes the updated value back into the heap.
How to solve Construct Target Array With Multiple Sums in O(n log n)?
Use a max-heap to repeatedly process the largest value. Let totalSum be the array sum and max be the largest element. Compute rest = totalSum - max and reduce the largest value using prev = max % rest. Push the updated value back into the heap and continue until all values become 1 or an invalid state occurs.
What is the best approach for Construct Target Array With Multiple Sums?
The optimal solution uses a greedy reverse simulation with a max-heap (priority queue). Always remove the largest value, compute the remaining sum of the array, and determine the previous value using modulo. This keeps operations efficient and results in O(n log n) time complexity with O(n) space.
Is Construct Target Array With Multiple Sums asked at Google/Amazon/Meta?
Construct Target Array With Multiple Sums appears in interviews at companies that emphasize algorithmic reasoning such as Google, Amazon, and Meta. The problem tests greedy thinking, reverse simulation, and efficient use of heaps or priority queues.
What data structure is used in Construct Target Array With Multiple Sums?
The primary data structure is a max-heap (priority queue) to efficiently retrieve and update the largest element. The algorithm also relies on maintaining the total array sum and performing modulo arithmetic to compress multiple reverse operations.
What is the time complexity of Construct Target Array With Multiple Sums?
The optimal max-heap solution runs in O(n log n) time because each step extracts and reinserts the largest element into a priority queue. Space complexity is O(n) for storing the heap. A sorting-based implementation can degrade to O(k * n log n) due to repeated sorting.

Ready to solve this problem?

Practice Construct Target Array With Multiple Sums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Amount of Time to Fill Cups