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.

Description Hints 2 Solution Video 11:20

1354. Construct Target Array With Multiple Sums

Hard36.8% acceptance1 company

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 * 10⁴
1 <= target[i] <= 10⁹

Asked at 1 company

Quora

Topics

Array Heap (Priority Queue)

Hints open one at a time

Hint 1

Given that the sum is strictly increasing, the largest element in the target must be formed in the last step by adding the total sum in the previous step. Thus, we can simulate the process in a reversed way.

Hint 2

Subtract the largest with the rest of the array, and put the new element into the array. Repeat until all elements become one

11:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution