Construct Target Array With Multiple Sums: Reverse Simulation with Max-Heap

You are given an array target of positive integers. Starting with an array of all ones (same length as target), you can perform the following operation any number of times: pick any element and replace it with the sum of all elements in the array. Return True if you can construct target from the starting array, or False otherwise.

This is LeetCode 1354: Construct Target Array With Multiple Sums, and it is a tricky hard problem that becomes elegant once you see the key insight: work backwards.

Example: target = [9, 3, 5]. Can we build this from [1, 1, 1]?

Why this problem matters

At first glance, this looks like you need to simulate the forward process, trying every possible sequence of replacements. That would be exponential. The trick is to reverse the problem entirely. Instead of building up from [1, 1, 1], you tear down from the target array. This "reverse simulation" technique shows up in many problems where the forward direction has too many choices but the backward direction is deterministic.

The problem also teaches you how a max-heap can guide a greedy process. The largest element in the array is always the one that was replaced last, so you always know exactly which element to undo. This makes the reverse simulation both correct and efficient.

The key insight

Think about it backwards. The largest element in the target array must have been the most recently replaced element. Why? Because when you replace an element with the total sum, the new value is strictly larger than every other element (since the sum includes all of them). So the largest value was the last replacement.

To reverse that step, you need to figure out what the element was before it was replaced. If the current max is M and the sum of all other elements is rest, then the total before the replacement was rest + prev_value. The replacement set the element to rest + prev_value, which equals M. So prev_value = M - rest.

But there is a catch. If M is much larger than rest, you would have to subtract rest many times. For example, if target = [1, 1000000000], naively subtracting 1 repeatedly would be way too slow. You can skip all those repeated subtractions with modulo: prev_value = M % rest.

Use a max-heap to always grab the largest element efficiently. Pop the max, compute the previous value, push it back, and repeat until every element is 1 (success) or you detect an impossible case.

The solution

import heapq

def is_possible(target: list[int]) -> bool:
    total = sum(target)
    heap = [-x for x in target]
    heapq.heapify(heap)

    while -heap[0] > 1:
        largest = -heapq.heappop(heap)
        rest = total - largest
        if rest <= 0 or rest >= largest:
            return False
        if rest == 1:
            return True
        largest %= rest
        if largest == 0:
            return False
        heapq.heappush(heap, -largest)
        total = rest + largest

    return True

Let's walk through what each piece does.

The heap setup. Python's heapq is a min-heap, so we negate all values to simulate a max-heap. After heapifying, -heap[0] is always the current maximum.

The main loop. We keep going as long as the max element is greater than 1. If every element is 1, we have reached the starting array and return True.

Pop the max. We extract the largest element and compute rest, the sum of all other elements. This is just total - largest.

Early termination checks. If rest is 0 or negative, the input is invalid (this can happen with single-element arrays containing 1). If rest >= largest, we cannot make progress because the previous value would be non-positive, which is impossible since all values must be positive.

The modulo optimization. Instead of subtracting rest from largest one step at a time, we use largest %= rest to jump straight to the final remainder. This is the key optimization that prevents TLE on cases like [1, 1000000000].

Check for zero remainder. If largest % rest == 0, the previous value would be 0, which is invalid. Return False.

Push back and update total. Push the computed previous value back into the heap and update the running total.

Visual walkthrough

Let's trace through the reverse simulation for target = [9, 3, 5]. At each step, we pop the max from the heap, compute the previous value using modulo, and push it back.

Each step is deterministic. The largest element tells you exactly which replacement to undo, and the modulo gives you the previous value. When every element reaches 1, you know the target was constructible.

Complexity analysis

Time is O(n log n log M) where n is the length of the target array and M is the maximum value in it. Each heap operation is O(log n). The number of iterations is bounded by O(n log M) because the modulo operation reduces the largest element by at least half each time it wraps around (similar to the GCD analysis). In practice, the modulo makes this very fast.

Space is O(n) for the heap.

The building blocks

1. Max-heap with reverse simulation

The pattern of using a max-heap to always process the largest element, reversing one operation at a time:

import heapq

heap = [-x for x in values]
heapq.heapify(heap)
while -heap[0] > target_val:
    largest = -heapq.heappop(heap)
    new_val = transform(largest)
    heapq.heappush(heap, -new_val)

This pattern appears whenever you need to greedily process the largest element and simulate a process in reverse. The max-heap ensures you always pick the right element to undo.

2. Modulo to skip repeated subtractions

When the same subtraction would happen many times in a row, replace the loop with a single modulo operation:

while value > threshold:
    value -= step
# becomes:
value %= step
if value == 0:
    value = step

This optimization appears in GCD computation, the Euclidean algorithm, and problems where you repeatedly subtract a fixed amount. Whenever you see a loop that subtracts the same value, think modulo.

Edge cases

Before submitting, think through these scenarios:

• Single element [1]: already all ones. Return True.
• Single element [n] where n > 1: rest = 0. You can never reduce a single element greater than 1. Return False (unless n is exactly equal to the array length, which for a single element means target = [1]).
• All ones [1, 1, 1]: the max is already 1, so the while loop never executes. Return True.
• Large values [1, 1000000000]: without modulo this would TLE. With modulo, 1000000000 % 1 = 0, but rest = 1 triggers the early return True before the modulo.
• Impossible cases [2, 2]: total = 4, max = 2, rest = 2. rest >= largest, so return False. You cannot construct [2, 2] because any replacement from [1, 1] would produce [2, 1] or [1, 2], never [2, 2].
• Even reduction [8, 5]: total = 13, max = 8, rest = 5, prev = 8 % 5 = 3. Array becomes [3, 5]. Then max = 5, rest = 3, prev = 5 % 3 = 2. Array becomes [3, 2]. Then [1, 2]. Then [1, 1]. Return True.

From understanding to recall

The reverse simulation idea is the kind of insight that clicks immediately when you read it but vanishes when you sit down to code it under pressure. The details that trip people up are the termination conditions. When do you return False? What if rest is 1? What about the modulo producing 0?

These are not conceptual gaps. They are recall gaps. You understand the algorithm perfectly, but the specific checks slip away after a week. Spaced repetition fixes this. You practice writing the solution from scratch, and each time you reinforce the exact sequence of checks: rest <= 0, rest >= largest, rest == 1, largest == 0 after modulo.

CodeBricks breaks this problem into its building blocks, the max-heap reverse simulation and the modulo optimization, and drills them independently. After a few rounds at increasing intervals, the pattern becomes automatic.

Related posts

• Kth Largest Element: Heap vs Quickselect - The foundational max-heap/min-heap problem that teaches heap mechanics
• Top K Frequent Elements - Another heap problem where you maintain a size-k heap to efficiently track top elements
• Meeting Rooms II - Uses a min-heap to greedily process intervals, showing another application of heap-driven simulation