Construct Target Array With Multiple Sums solution and explanation
9 more videos on this problem
Construct Target Array With Multiple Sums || LeetcodePepcoding · 11:20 · 6K views
Construct Target Array With Multiple Sums | Live Coding with Explanation | Leetcode - 1354Algorithms Made Easy · 14:46 · 6K views
Construct Target Array With Multiple Sums | Leetcode 1354 Hard | Live coding session | Leetcode HardCoding Decoded · 15:31 · 2K views
LeetCode - 1354. Construct Target Array With Multiple Sums | Day 9 May ChallengeAditya Mahajan · 11:54 · 1K views
Construct Target Array With Multiple Sums | LeetCode 1354 | Coders CampCoders Camp · 9:56 · 1K views
LeetCode 1354. Construct Target Array With Multiple SumsHappy Coding · 25:05 · 1K views
Leetcode - Construct Target Array With Multiple Sums (Python)Timothy H Chang · 10:38 · 1K views
1354. Construct Target Array With Multiple SumsTech Adora by Nivedita · 16:15 · 888 views
Leetcode 1354 Construct Target Array With Multiple Sums | | Checkout Coding Decoded SDE SheetCoding Decoded · 1:38 · 861 views
Daily Leetcode #815: Jun 24, 2022 - 1354. Construct Target Array With Multiple SumsProgramming Live with Larry · 31:41 · 523 views
The problem
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
xbe the sum of all elements currently in your array. - choose index
i, such that0 <= i < nand set the value ofarrat indexitox. - 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.length1 <= n <= 5 * 1041 <= 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.
- Create a max-heap and compute the total sum of the target array.
- Iteratively replace the largest element max with max % rest, where rest is the sum of all elements except max.
- Continue this process until all elements are ones or it's impossible to proceed.
import heapq
def isPossible(target):
total = sum(target)
target = [-x for x in target]
heapq.heapify(target)
while True:
largest = -heapq.heappop(target)
total -= largest
if largest == 1 or total == 1:
return True
if largest < total or total == 0 or largest % total == 0:
return False
largest %= total
total += largest
heapq.heappush(target, -largest)
print(isPossible([9, 3, 5]))import java.util.PriorityQueue;
public class Solution {
public boolean isPossible(int[] target) {
long total = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int num : target) {
total += num;
pq.offer(num);
}
while (pq.peek() != 1) {
int largest = pq.poll();
total -= largest;
if (total == 1 || largest <= total) return false;
largest %= total;
total += largest;
pq.offer(largest > 0 ? largest : (int) total);
}
return true;
}
public static void main(String[] args) {
int[] target = {9, 3, 5};
Solution sol = new Solution();
System.out.println(sol.isPossible(target));
}
}#include <iostream>
#include <vector>
#include <queue>
bool isPossible(std::vector<int>& target) {
long total = 0;
std::priority_queue<int> pq;
for(int num : target) {
total += num;
pq.push(num);
}
while(pq.top() != 1) {
int largest = pq.top(); pq.pop();
total -= largest;
if(total == 1 || largest % total == 0) return false;
largest %= total;
total += largest;
pq.push(largest);
}
return true;
}
int main() {
std::vector<int> target = {9, 3, 5};
std::cout << (isPossible(target) ? "true" : "false") << std::endl;
return 0;
}function isPossible(target) {
let total = target.reduce((a, b) => a + b, 0);
target = target.map(x => -x);
target.sort((a, b) => a - b);
while (-target[0] !== 1) {
let largest = -target.shift();
total -= largest;
if (largest < total || total < 1 || largest % total === 0) {
return false;
}
largest %= total;
total += largest;
target.push(-largest);
target.sort((a, b) => a - b);
}
return true;
}
console.log(isPossible([9, 3, 5]));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int cmp(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
bool isPossible(int* target, int targetSize) {
long sum = 0;
for(int i = 0; i < targetSize; i++) sum += target[i];
qsort(target, targetSize, sizeof(int), cmp);
while(target[0] != 1) {
long max = target[0], rest = sum - max;
if (rest == 0 || max <= rest) return false;
int new_value = (int) (max % rest == 0 ? rest : max % rest);
if(new_value == 0) return false;
sum = sum - max + new_value;
target[0] = new_value;
qsort(target, targetSize, sizeof(int), cmp);
}
return true;
}
int main() {
int target[] = {9,3,5};
int targetSize = sizeof(target) / sizeof(target[0]);
printf("%s\n", isPossible(target, targetSize) ? "true" : "false");
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public bool IsPossible(int[] target) {
long total = 0;
PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
foreach (int num in target) {
total += num;
pq.Enqueue(num, -num);
}
while (pq.Peek() != 1) {
int largest = pq.Dequeue();
total -= largest;
if (total <= 1 || largest <= total || largest % total == 0) return false;
largest %= total;
total += largest;
pq.Enqueue(largest, -largest);
}
return true;
}
static void Main() {
var sol = new Solution();
Console.WriteLine(sol.IsPossible(new int[] {9, 3, 5}));
}
}This Python solution takes advantage of the heapq library to create a max-heap by using negative values since Python only provides a min-heap by default. The overall strategy is to continually control and transform the largest element, ensuring the constraints allow the construction of the target from the base array.
The time complexity is O(n log n * log maxValue), and the space complexity is O(n) given the priority queue's storage.
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:
- Sort the target array descending and compute the total sum.
- Continue to find the largest element and replace it by modding it with the rest of the sum, adjusting the total sum.
- Return the possibility of the transformation when all elements are reduced to one, or halt if impossible.
def isPossible(target):
total = sum(target)
target.sort(reverse=True)
while target[0] != 1:
max_val = target[0]
rest = total - max_val
if rest == 0 or max_val <= rest:
return False
new_val = max_val % rest
if new_val == 0:
return False
target[0] = new_val
total = total - max_val + new_val
target.sort(reverse=True)
return True
if __name__ == '__main__':
target = [8, 5]
print(isPossible(target))import java.util.Arrays;
public class Solution {
public boolean isPossible(int[] target) {
long sum = 0;
for (int x : target) sum += x;
Arrays.sort(target);
while (target[target.length - 1] != 1) {
long largest = target[target.length - 1];
long rest = sum - largest;
if (rest == 0 || largest <= rest) return false;
int newValue = (int) (largest % rest);
if (newValue == 0) return false;
sum = sum - largest + newValue;
target[target.length - 1] = newValue;
Arrays.sort(target);
}
return true;
}
public static void main(String[] args) {
Solution obj = new Solution();
int[] target = {8, 5};
System.out.println(obj.isPossible(target) ? "true" : "false");
}
}#include <iostream>
#include <vector>
#include <algorithm>
bool isPossible(std::vector<int>& target) {
long sum = 0;
for (int num : target) sum += num;
std::sort(target.begin(), target.end(), std::greater<int>());
while (target[0] != 1) {
long largest = target[0], rest = sum - largest;
if (rest == 0 || largest <= rest) return false;
int new_value = largest % rest;
if (new_value == 0) return false;
target[0] = new_value;
sum = sum - largest + new_value;
std::sort(target.begin(), target.end(), std::greater<int>());
}
return true;
}
int main() {
std::vector<int> target = {8, 5};
std::cout << (isPossible(target) ? "true" : "false") << std::endl;
return 0;
}function isPossible(target) {
let total = target.reduce((a, b) => a + b, 0);
target.sort((a, b) => b - a);
while (target[0] !== 1) {
const largest = target[0];
const rest = total - largest;
if (rest === 0 || largest <= rest) return false;
const newValue = largest % rest;
if (newValue === 0) return false;
target[0] = newValue;
total = total - largest + newValue;
target.sort((a, b) => b - a);
}
return true;
}
console.log(isPossible([8, 5]));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int cmp(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
bool isPossible(int* target, int targetSize) {
long sum = 0;
for(int i = 0; i < targetSize; i++) sum += target[i];
qsort(target, targetSize, sizeof(int), cmp);
while(target[0] != 1) {
long max = target[0], rest = sum - max;
if (rest == 0 || max <= rest) return false;
int new_value = (int) (max % rest == 0 ? rest : max % rest);
if(new_value == 0) return false;
sum = sum - max + new_value;
target[0] = new_value;
qsort(target, targetSize, sizeof(int), cmp);
}
return true;
}
int main() {
int target[] = {8, 5};
int targetSize = sizeof(target) / sizeof(target[0]);
printf("%s\n", isPossible(target, targetSize) ? "true" : "false");
return 0;
}using System;
using System.Linq;
class Solution {
public bool IsPossible(int[] target) {
long sum = target.Sum();
Array.Sort(target, (a, b) => b.CompareTo(a));
while (target[0] != 1) {
int largest = target[0];
long rest = sum - largest;
if (rest == 0 || largest <= rest) return false;
int newValue = (int) (largest % rest);
if (newValue == 0) return false;
target[0] = newValue;
sum = sum - largest + newValue;
Array.Sort(target, (a, b) => b.CompareTo(a));
}
return true;
}
static void Main() {
int[] target = {8, 5};
Console.WriteLine(new Solution().IsPossible(target) ? "true" : "false");
}
}The Python implementation follows a predictable yet potent approach by reversing and resorting the target array, ensuring orderly checks for the possibility of reaching the target by modulating the largest (lead) element successful tracking of inverting the initial transformation steps.
Time complexity is O(n log n * log maxValue), space complexity is O(1).
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.
function isPossible(target: number[]): boolean {
const pq = new MaxPriorityQueue<number>();
let s = 0;
for (const x of target) {
s += x;
pq.enqueue(x);
}
while (pq.front() > 1) {
const mx = pq.dequeue();
const t = s - mx;
if (t < 1 || mx - t < 1) {
return false;
}
const x = mx % t || t;
pq.enqueue(x);
s = s - mx + x;
}
return true;
}func isPossible(target []int) bool {
pq := &hp{target}
s := 0
for _, x := range target {
s += x
}
heap.Init(pq)
for target[0] > 1 {
mx := target[0]
t := s - mx
if t < 1 || mx-t < 1 {
return false
}
x := mx % t
if x == 0 {
x = t
}
target[0] = x
heap.Fix(pq, 0)
s = s - mx + x
}
return true
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (hp) Pop() (_ any) { return }
func (hp) Push(any) {}use std::collections::BinaryHeap;
impl Solution {
pub fn is_possible(target: Vec<i32>) -> bool {
let mut pq = BinaryHeap::from(target.clone());
let mut s: i64 = target.iter().map(|&x| x as i64).sum();
while let Some(&mx) = pq.peek() {
if mx == 1 {
break;
}
let mx = pq.pop().unwrap() as i64;
let t = s - mx;
if t < 1 || mx - t < 1 {
return false;
}
let x = if mx % t == 0 { t } else { mx % t };
pq.push(x as i32);
s = s - mx + x;
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Max-Heap Backtracking | The time complexity is O(n log n * log maxValue), and the space complexity is O(n) given the priority queue's storage. |
| Approach 2: Iterative Modulo with Sorting | Time complexity is O(n log n * log maxValue), space complexity is O(1). |
| Reverse Construction + Priority Queue (Max Heap) | – |
Complexity analysis
| 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 |
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.