LeetCode 1354 - Construct Target Array With Multiple Sums

Difficulty: 🔴 Hard
Topics: Array, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks whether it is possible to construct a given target array from an initial array arr of the same length, consisting entirely of 1s, using a specific transformation repeatedly. The transformation involves selecting any index i and replacing arr[i] with the sum of all current elements in arr.

In other words, starting from [1, 1, 1, ..., 1], at each step you can pick an element and make it equal to the current total sum of the array. The goal is to determine whether we can reach the target array using this operation.

The input target is an array of length n (up to 50,000), and each element can be as large as 10^9. The output is a boolean: true if it is possible to construct the target array, false otherwise. The constraints suggest we need an efficient solution, as simulating all possible operations directly would be too slow for large arrays.

Important edge cases include target arrays that are already all ones, arrays with only one element, and arrays that are impossible to reach because some values are smaller than the sum of the rest of the array.

Approaches

A brute-force approach would attempt to simulate the process of repeatedly picking an index and updating its value until we reach the target array. At each step, we would try all possibilities for which index to replace. While this method is correct in principle, it is exponentially slow because the number of possible operations grows rapidly with array length and element values.

The key observation that allows an optimal solution is to work backwards from the target array. At each step, the largest element in the target array must have been created by replacing some element with the sum of the previous array. Therefore, we can use a max heap to repeatedly reduce the largest element by the sum of the remaining elements, effectively reversing the transformation until we reach an array of all ones.

This approach works because in each step, the largest number in the target must come from the sum of all other numbers plus the previous value at that index. By continually reducing the largest number, we can check if it is possible to reach a starting array of ones.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(?)	O(n)	Simulate every possible replacement, exponential in n
Optimal (Max Heap, Reverse Simulation)	O(n log n)	O(n)	Use a max heap to always reduce the largest element; simulate in reverse

Algorithm Walkthrough

Convert the target array into a max heap, storing negative values because Python’s heapq is a min-heap by default.
Compute the total sum of the array.
Repeat the following until the largest element is 1:
Extract the largest element from the heap (convert back to positive).
Compute the sum of the rest of the elements as rest = total_sum - largest.
If rest is 1, we can always construct the array by repeatedly subtracting 1 from the largest element.
If rest is zero or larger than the largest element, return False because it is impossible.
Compute the previous value of the largest element as largest % rest.
If this previous value is zero or does not change the largest element, return False.
Push the previous value back into the heap and update the total sum.
If all elements eventually reduce to 1, return True.

Why it works: By always reducing the largest element, we ensure that each step reverses the operation used to construct the array. The algorithm maintains the invariant that the total sum minus the largest element represents the sum of all other elements at that step. If this invariant breaks, it is impossible to reach the starting array.

Python Solution

import heapq
from typing import List

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        if len(target) == 1:
            return target[0] == 1
        
        total_sum = sum(target)
        # Python heapq is a min-heap, use negatives for max-heap
        max_heap = [-x for x in target]
        heapq.heapify(max_heap)
        
        while True:
            largest = -heapq.heappop(max_heap)
            rest = total_sum - largest
            if largest == 1 or rest == 1:
                return True
            if rest == 0 or largest <= rest:
                return False
            previous = largest % rest
            if previous == 0:
                return False
            heapq.heappush(max_heap, -previous)
            total_sum = rest + previous

The implementation first checks for the edge case of a single-element array. It then initializes a max heap using negative values. In the loop, we repeatedly reduce the largest value and update the total sum. The key operations involve checking if the remaining sum can logically produce the current largest element and updating the heap accordingly.

Go Solution

package main

import (
    "container/heap"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // max-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func isPossible(target []int) bool {
    if len(target) == 1 {
        return target[0] == 1
    }
    
    totalSum := 0
    h := &IntHeap{}
    for _, x := range target {
        totalSum += x
        *h = append(*h, x)
    }
    heap.Init(h)
    
    for {
        largest := heap.Pop(h).(int)
        rest := totalSum - largest
        if largest == 1 || rest == 1 {
            return true
        }
        if rest == 0 || largest <= rest {
            return false
        }
        previous := largest % rest
        if previous == 0 {
            return false
        }
        heap.Push(h, previous)
        totalSum = rest + previous
    }
}

The Go solution mirrors the Python version. It defines a max-heap type using container/heap, pushes all elements, and repeatedly reduces the largest value while checking feasibility. The main difference is Go requires implementing the heap interface explicitly.

Worked Examples

Example 1: target = [9, 3, 5]

Step	Max	Rest	Previous	Heap State
Initial	9	8	1	[5,3,1]
Next	5	4	1	[3,1,1]
Next	3	2	1	[1,1,1]
Done	All 1	-	-	[1,1,1]

Example 2: target = [1,1,1,2]

Step	Max	Rest	Previous	Heap State
Initial	2	3	2%3=2	Condition fails

Example 3: target = [8,5]

Step	Max	Rest	Previous	Heap State
Initial	8	5	3	[5,3]
Next	5	3	2	[3,2]
Next	3	2	1	[2,1]
Next	2	1	1	[1,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each heap operation is log n and we may perform it for each reduction step.
Space	O(n)	Storing the heap of size n.

The dominant cost is the max-heap operations. Each element can only be reduced a limited number of times before reaching 1, keeping total operations proportional to n log n in practice.

Test Cases

# Provided examples
assert Solution().isPossible([9,3,5]) == True
assert Solution().isPossible([1,1,1,2]) == False
assert Solution().isPossible([8,5]) == True

# Edge cases
assert Solution().isPossible([1]) == True  # single element 1
assert Solution().isPossible([2]) == False # single element not 1
assert Solution().isPossible([1,1,1,1]) == True  # all ones
assert Solution().isPossible([1,1000000000]) == False  # very large element
assert Solution().isPossible([2,1]) == True  # minimal transformation

| Test | Why |