1354. Construct Target Array With Multiple Sums

HardArrayHeap (Priority Queue)
Leetcode Link

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, where 0 <= i < n, and update the value at index i in arr to x.
  • 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

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:

  1. Special Case Check: If the length of the target array is 1, the only way to have a valid target is if the lone element is also 1. This returns True immediately in such a scenario.

  2. Initialize a max heap using the negative values of the target array elements and get the sum of all elements in target.

  3. 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 return True immediately because this implies the array can be reduced to all 1'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 return False.
    • Push the negated updated value back onto the max heap.
    • Update the total sum with the new value of the updated element.

  4. If the loop concludes without returning False, this means all elements have been reduced to 1 (or were already 1), so we return True.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let’s walk through a small example to illustrate the solution approach:

Suppose we have a target array of [1, 3, 5].

  1. Since there is more than one element in the target, we don’t return True from the special case check.

  2. 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 is 1+3+5=9.

  3. Enter the while loop and start processing the heap:

    • Extract the largest element, -5 (which is 5 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 return True 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.

  4. Repeat the process until the largest element is no longer greater than 1:

    • Extract -3, the largest element now, giving us 3.
    • 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 to 2 + 1 = 3.

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
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

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), where n 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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Recommended Readings

Heap Fundamentals

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

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.

←
↑TA 👨‍🏫