1354. Construct Target Array With Multiple Sums
Problem Description
The LeetCode problem provides an array called target
which contains n
integers. The objective is to determine if this target
array can be formed from an initial array called arr
, which consists of n
elements each with a value of 1. To transform the arr
into the target
, a specific procedure can be followed:
- Calculate the sum (
x
) of all elements in your current array. - Choose an index
i
, where0 <= i < n
, and update the value at indexi
inarr
tox
. - Repeat this process as necessary.
The goal is to find out if the target
array can be created from the initial arr
by following the aforementioned procedure. The function should return true
if it is possible, or false
if it is not.
Intuition
To tackle this problem, we need to think about it in reverse. Instead of starting from the initial array and trying to build up to the target
, we'll start from the target
and attempt to reduce it to the initial array. Why? The operations described in the problem tend to exponentially increase the values in the array, making it challenging to directly reach the target
array values.
Since we're attempting to reverse the operation, here are the steps that lead us to the intuitive solution:
- We use a max heap to keep track of the largest element in the
target
array because our operation always works on the current largest element. - At each step, we replace the largest element with the difference between it and the sum of the rest of the elements. This effectively simulates the reverse operation.
- If the largest element happens to be 1 or if the sum of the other elements is 1, we've effectively reached our starting array of all 1's, so we can return
true
immediately. - We must also consider a couple of special cases where our problem can have no solution:
- If the largest element remains the same after the modulo operation or becomes 0, we can't reach our goal.
- Since the target array was built up from an array of ones, it's impossible to make the largest number smaller than the sum of the other numbers - if that happens, we cannot build the
target
from the initial array.
While iterating through the max heap process, if all elements in the target
can be reduced to 1, it's possible to construct the target
from the arr
. If we hit a point where elements can't be reduced further following the rules, it's impossible, and we return false
.
Learn more about Heap (Priority Queue) patterns.
Solution Approach
The implementation of the solution uses a max heap data structure to manage the target
array during the conversion process. This is because we need to frequently access and update the largest element, and a max heap enables us to do this efficiently. The Python heapq
module, which only supports min heaps by default, is used to create a max heap by inserting the negation of each number in the target
array.
Here's a detailed walk-through of the implementation steps:
-
Special Case Check: If the length of the
target
array is1
, the only way to have a valid target is if the lone element is also1
. This returnsTrue
immediately in such a scenario. -
Initialize a max heap using the negative values of the
target
array elements and get the sum of all elements intarget
. -
While the largest element (the root of the max heap) is greater than
1
, we perform the following actions:- Retrieve and negate the largest element from the max heap (to convert it back to a positive number).
- Calculate the sum of the remaining elements by subtracting the largest element from the total sum.
- Check if the sum of the remaining elements is
1
. If so, we returnTrue
immediately because this implies the array can be reduced to all1's
(as per the problem description). - Calculate the updated value for the largest element by taking the modulo of it with the sum of the remaining elements.
- Check if the updated value is
0
or didn't change. If either is true, we cannot form the target array and returnFalse
. - Push the negated updated value back onto the max heap.
- Update the total sum with the new value of the updated element.
-
If the loop concludes without returning
False
, this means all elements have been reduced to1
(or were already1
), so we returnTrue
.
The algorithm utilized here involves both elements of heap manipulation and a clever mathematical trick of working in reverse. The modulo operation serves as a substitute for multiple iterations of the described procedure in the problem, thus greatly optimizing the number of steps required to reach the solution.
Although the problem appears to be a forward problem, the implemented solution uses backward reasoning. By considering how we could've arrived at the target
array, we can more easily determine if it's possible or not. This form of reasoning is often applied in problems that involve building or transforming collections of elements, especially when the transformations are complex or expansive.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Letās walk through a small example to illustrate the solution approach:
Suppose we have a target
array of [1, 3, 5]
.
-
Since there is more than one element in the
target
, we donāt returnTrue
from the special case check. -
Initialize a max heap with the negative values of the
target
array to help us easily find and extract the maximum element. After inserting the elements, our heap will look like[-5, -3, -1]
. The total sum at this point is1+3+5=9
. -
Enter the while loop and start processing the heap:
- Extract the largest element,
-5
(which is5
when converted back to positive). - Calculate the sum of the remaining elements,
9 - 5 = 4
. - The sum of the remaining elements is not
1
, so we do not returnTrue
at this point. - Update the largest element's value by taking
5 % 4 = 1
. - Check if the updated value is
0
or did not change (Neither is true in this case). - Push the negated updated value back onto the heap, which becomes
[-3, -1, -1]
. - Update the total sum to
4 + 1 = 5
.
- Extract the largest element,
-
Repeat the process until the largest element is no longer greater than
1
:- Extract
-3
, the largest element now, giving us3
. - The sum of the rest is
5 - 3 = 2
. - Update the largest element's value with
3 % 2 = 1
. - Check for the unchanged or zero value (None are true).
- The heap is now updated to
[-1, -1, -1]
and the total sum to2 + 1 = 3
.
- Extract
This process continues, and each time we are either left with the heap elements being all 1
or finding a situation where the largest number is modulo'd to 1. When all elements in the heap are 1
, or the sum of the rest of elements becomes 1
, we exit the while loop and return True
.
For our example, after inserting all the negated updated values (-1 for each), the heap is [-1, -1, -1]
, and the sum is 3
(which equals the number of elements in the heap). Since the loop has concluded and we didnāt encounter a condition that would return False
, we return True
: it is indeed possible to construct the target
from an array of all 1
's using the described procedure.
Solution Implementation
1from heapq import heapify, heappop, heappush
2from typing import List
3
4class Solution:
5 def isPossible(self, target: List[int]) -> bool:
6 # If the target array has only one element, it should be 1 to form a valid array.
7 if len(target) == 1:
8 return target[0] == 1
9
10 # Calculate the sum of elements in the target array.
11 total_sum = sum(target)
12 # Convert target elements to negative numbers because Python has a min heap by default.
13 max_heap = [-num for num in target]
14 # Transform the array into a heap in-place.
15 heapify(max_heap)
16
17 while -max_heap[0] > 1:
18 # Pop the largest element from the heap.
19 max_element = -heappop(max_heap)
20 # Calculate the sum of the rest of the elements.
21 remaining_sum = total_sum - max_element
22
23 # If the remaining sum is 1, it is always possible to build the array.
24 if remaining_sum == 1:
25 return True
26
27 # Find the updated value of the target's largest element.
28 updated_element = max_element % remaining_sum
29
30 # If updated_element is 0 or the same as the original max_element, there won't be any progress.
31 if updated_element == 0 or updated_element == max_element:
32 return False
33
34 # Push the updated element back into the heap and update the total sum.
35 heappush(max_heap, -updated_element)
36 total_sum = total_sum - max_element + updated_element
37
38 # All elements have been reduced to 1, hence the original array can be constructed.
39 return True
40
1import java.util.PriorityQueue;
2
3public class Solution {
4 public boolean isPossible(int[] target) {
5 // If the target array has only one element, it should be 1 to form a valid array.
6 if (target.length == 1) {
7 return target[0] == 1;
8 }
9
10 // Calculate the sum of elements in the target array.
11 long totalSum = 0;
12 // Use a max heap in Java by providing a custom comparator.
13 PriorityQueue<Long> maxHeap = new PriorityQueue<>((a, b) -> Long.compare(b, a));
14 for (int num : target) {
15 totalSum += num;
16 maxHeap.add((long)num);
17 }
18
19 while (maxHeap.peek() > 1) {
20 // Pop the largest element from the heap.
21 long maxElement = maxHeap.poll();
22 // Calculate the sum of the rest of the elements.
23 long remainingSum = totalSum - maxElement;
24
25 // If the remaining sum is 1, it is always possible to build the array.
26 if (remainingSum == 1) {
27 return true;
28 }
29
30 // Find the updated value of the target's largest element.
31 long updatedElement = maxElement % remainingSum;
32
33 // If updatedElement is 0 or does not change the maxElement, there won't be any progress.
34 if (updatedElement == 0 || updatedElement == maxElement) {
35 return false;
36 }
37
38 // Push the updated element back into the heap and update the total sum.
39 maxHeap.add(updatedElement);
40 totalSum = totalSum - maxElement + updatedElement;
41 }
42
43 // All elements have been reduced to 1, hence the original array can be constructed.
44 return true;
45 }
46}
47
1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6 bool isPossible(std::vector<int>& target) {
7 // If the target array has only one element, it should be 1 to form a valid array.
8 if (target.size() == 1) {
9 return target[0] == 1;
10 }
11
12 // Calculate the sum of elements in the target array.
13 long total_sum = 0;
14 for (int num : target) {
15 total_sum += num;
16 }
17
18 // Create a max heap from the target vector.
19 std::priority_queue<int> max_heap(target.begin(), target.end());
20
21 while (max_heap.top() > 1) {
22 // Pop the largest element from the heap.
23 int max_element = max_heap.top();
24 max_heap.pop();
25
26 // Calculate the sum of the rest of the elements.
27 long remaining_sum = total_sum - max_element;
28
29 // If the remaining sum is 1, it is always possible to build the array.
30 if (remaining_sum == 1) {
31 return true;
32 }
33
34 // Find the updated value of the target's largest element.
35 int updated_element = max_element % remaining_sum;
36
37 // If updated_element is 0 or the same as the original max_element, there won't be any progress.
38 if (updated_element == 0 || updated_element == max_element) {
39 return false;
40 }
41
42 // Push the updated element back into the heap and update the total sum.
43 max_heap.push(updated_element);
44 total_sum = total_sum - max_element + updated_element;
45 }
46
47 // All elements have been reduced to 1, hence the original array can be constructed.
48 return true;
49 }
50};
51
1// Importing the priority queue module for maintaining a max-heap
2import { PriorityQueue } from 'typescript-collections';
3
4// Function to check if it is possible to form a target array starting with an array full of 1's
5function isPossible(target: number[]): boolean {
6 // If the target array has only one element, it should be 1 to be formed by the described process.
7 if (target.length === 1) {
8 return target[0] === 1;
9 }
10
11 // Calculate the total sum of elements in the target array.
12 let totalSum: number = target.reduce((a, b) => a + b, 0);
13
14 // Create a max heap from the target array elements.
15 const maxHeap: PriorityQueue<number> = new PriorityQueue<number>((a, b) => b - a);
16 target.forEach(element => {
17 maxHeap.enqueue(element);
18 });
19
20 while (maxHeap.peek() > 1) {
21 // Extract the largest element from the heap.
22 const maxElement: number = maxHeap.dequeue();
23
24 // Calculate the sum of the remaining elements.
25 const remainingSum: number = totalSum - maxElement;
26
27 // If the remaining sum is 1, then it's always possible to reconstruct the array.
28 if (remainingSum === 1) {
29 return true;
30 }
31
32 // Find the updated value for the largest element in the target array.
33 const updatedElement: number = maxElement % remainingSum;
34
35 // If the updated element is 0 or doesn't make progress, return false.
36 if (updatedElement === 0 || updatedElement === maxElement) {
37 return false;
38 }
39
40 // Push the updated element back into the heap and update the total sum.
41 maxHeap.enqueue(updatedElement);
42 totalSum = totalSum - maxElement + updatedElement;
43 }
44
45 // The process has reduced all elements to 1, thus the target array can be constructed.
46 return true;
47}
48
Time and Space Complexity
Time Complexity
The primary operations here involve a while loop that runs as long as the maximum value in the heap is greater than 1
. In each iteration of the while loop, the operation complexity can be broken down as follows:
-
Extracting the maximum element from the heap:
O(log n)
, wheren
is the number of elements in the heap since a heap operation typically takes logarithmic time. -
Calculating
restSum
:O(1)
as it is just a subtraction operation. -
Calculating
updated
:O(1)
since it is a modulo operation. -
Insertion into the heap:
O(log n)
for the same reason as the extraction.
Considering the loop can run up to m
times, where m
is the value of the largest element in the initial array, in the average or worst case, the time complexity could be approximated to O(m log n)
. However, this is not strict because m
can decrease drastically in each iteration after the modulo operation is applied.
Space Complexity
The extra space used in the algorithm is for the heap. Since all elements of the input array must be stored, the space complexity is O(n)
, where n
is the size of the input array. There is no additional space usage that grows with the size of the input; hence the space complexity remains linear with respect to the input array size.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!