Leetcode 1354. Construct Target Array With Multiple Sums
Problem Explanation
This problem asks to determine whether we can form the given target array from the initial array that contains all 1's. The procedure we can perform is to compute the sum of the current array elements (let's call it sum) and select an index i from the target array, then replace the value at index i in the starting array with 'sum'.
The constraints on the length of the target array and the values in the target array make this problem quite challenging, as exhaustively trying every possible replacement of elements will not run within the time limits.
Walkthrough
Let's consider an example target array, [9, 3, 5]. The initial array is [1, 1, 1].
- In the first step, we can select index 2. The sum of the initial array is 3 so replace the element at index 2 in the initial array with sum: [1, 1, 3].
- In the second step, we can select index 1. The sum is now 5, so replace the value at index 1 with 5: [1, 5, 3].
- In the third step, we can select index 0. The sum is now 9, so replace the value at index 0 with 9: [9, 5, 3].
- Now the starting array equals to the target array.
Approach
The main idea for the solution is to maintain a priority queue (also known as a heap) to keep track of the largest element in the current Array. This is because the sum we calculate will be used to replace the largest element in the array. But it's not enough just to reduce the largest number by sum. If the rest of the numbers in the array add up to less than the largest number, we will end up in an infinite loop of decreasing the largest number and increasing the sum. To avoid this, we take the largest number modulo the sum of the rest of the array numbers, updating the sum in the process. This step "simulates" the process of reducing the largest number back to the sum of the rest of the array, then adding the sum back to one of the numbers.
We do these updates until the largest number is 1, or we can't perform updates without violating the constraints or changing the largest number. If the largest number is 1, it means that all numbers are 1, and we have the starting state of the problem.
Python Solution
1 2python 3import heapq 4 5class Solution: 6 def isPossible(self, target): 7 total = sum(target) 8 maxHeap = [-ele for ele in target] 9 heapq.heapify(maxHeap) 10 11 while True: 12 ele = -heapq.heappop(maxHeap) 13 total -= ele 14 if ele == 1 or total == 1: 15 return True 16 if ele < total or total == 0 or ele % total == 0: 17 return False 18 ele %= total 19 total += ele 20 heapq.heappush(maxHeap, -ele)
Java Solution
1 2java 3public class Solution { 4 public boolean isPossible(int[] target) { 5 long total = 0; 6 int n = target.length; 7 PriorityQueue<Long> pq = new PriorityQueue<>(n, (a, b) -> Long.compare(b, a)); 8 for (int a : target) { 9 total += a; 10 pq.add((long) a); 11 } 12 while (true) { 13 long a = pq.poll(); 14 total -= a; 15 if (a == 1 || total == 1) 16 return true; 17 if (a < total || total == 0 || a % total == 0) 18 return false; 19 a %= total; 20 total += a; 21 pq.add(a); 22 } 23 } 24}
Javascript Solution
1
2javascript
3/**
4 * @param {number[]} target
5 * @return {boolean}
6 */
7var isPossible = function(target) {
8 let sum = target.reduce((a, b) => a + b, 0);
9 let maxHeap = new MaxHeap(target);
10
11 while (true) {
12 let num = maxHeap.poll();
13 sum -= num;
14 if (num === 1 || sum === 1) {
15 return true;
16 }
17 if (num < sum || sum === 0 || num % sum === 0) {
18 return false;
19 }
20 num %= sum;
21 sum += num;
22 maxHeap.offer(num);
23 }
24};
C# Solution
1 2csharp 3public class Solution { 4 public bool IsPossible(int[] target) { 5 long total = 0; 6 int n = target.Length; 7 var maxHeap = new MaxHeap(n); 8 foreach (var num in target) 9 { 10 total += num; 11 maxHeap.Add(num); 12 } 13 while (true) 14 { 15 var num = maxHeap.Poll(); 16 total -= num; 17 if (num == 1 || total == 1) 18 return true; 19 if (num < total || total == 0 || num % total == 0) 20 return false; 21 num %= total; 22 total += num; 23 maxHeap.Add(num); 24 } 25 } 26}
C++ Solution
1 2cpp 3class Solution { 4public: 5 bool isPossible(vector<int>& target) { 6 long total = 0; 7 int n = target.size(); 8 priority_queue<long> pq; 9 for (int a : target) { 10 total += a; 11 pq.push(a); 12 } 13 while (true) { 14 long a = pq.top(); pq.pop(); 15 total -= a; 16 if (a == 1 || total == 1) 17 return true; 18 if (a < total || total == 0 || a % total == 0) 19 return false; 20 a %= total; 21 total += a; 22 pq.push(a); 23 } 24 } 25};
For JavaScript and C#
JavaScript and C# do not have a built-in max heap structure. The following are heap solutions for these languages.
JavaScript Solution
We create a custom class for the heap with methods to add to the heap, remove from the heap, and get the max value.
1
2javascript
3class MaxHeap {
4 constructor(array) {
5 this.array = array;
6 this.size = array.length;
7 this.buildHeap();
8 }
9
10 buildHeap() {
11 for (let i = Math.floor(this.size / 2) - 1; i >= 0; i--) {
12 this.heapify(i);
13 }
14 }
15
16 heapify(i) {
17 while (true) {
18 let left = 2 * i + 1;
19 let right = 2 * i + 2;
20 let largest = i;
21
22 if (left < this.size && this.array[left] > this.array[largest]) {
23 largest = left;
24 }
25
26 if (right < this.size && this.array[right] > this.array[largest]) {
27 largest = right;
28 }
29
30 if (i === largest) break;
31
32 [this.array[i], this.array[largest]] = [this.array[largest], this.array[i]];
33 i = largest;
34 }
35 }
36
37 poll() {
38 let max = this.array[0];
39 this.array[0] = this.array[this.size - 1];
40 this.size--;
41 this.heapify(0);
42 return max;
43 }
44
45 add(val) {
46 this.array[this.size] = val;
47 this.size++;
48 this.buildHeap();
49 }
50}
C# Solution
For C#, we can use SortedSet which keeps items sorted and duplicates are merged.
1 2csharp 3public class Solution { 4 public bool IsPossible(int[] target) { 5 long total = 0; 6 var maxHeap = new SortedSet<(int val, int index)>(); 7 for (int i = 0; i < target.Length; i++) { 8 total += target[i]; 9 maxHeap.Add((target[i], i)); 10 } 11 while (true) { 12 var max = maxHeap.Max; 13 maxHeap.Remove(max); 14 total -= max.val; 15 if (max.val == 1 || total == 1) return true; 16 if (max.val < total || total == 0 || max.val % total == 0) return false; 17 maxHeap.Add(((int)(max.val % total), max.index)); 18 total += max.val % total; 19 } 20 } 21}
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.