Skip to main content

1354 - Construct Target Array With Multiple Sums

Difficulty: Hard | Pattern: Greedy + Max-Heap (Reverse Simulation) | Company tags: Amazon, Google

Problem Statement​

You are given an array target of n integers. From a starting array arr consisting of all 1s, you may perform the following procedure:

  • Let x be the sum of all elements currently in your array.
  • Choose index i, such that 0 <= i < n, and make arr[i] equal to x.

You may repeat this procedure as many times as needed. Return true if it is possible to construct the target array from arr, otherwise return false.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: [1,1,1] → [1,1,3] → [1,5,3] → [9,5,3]

Example 2:

Input: target = [1,1,1,2]
Output: false

Algorithm Flow​

Approach: Reverse Simulation with Max-Heap — O(n log n + log(maxVal) × log n)​

Key insight: Work backwards. At each step, the largest element in target must have been the one most recently added. It was set to sum when added, so before that operation: prev = sum - (max_val - prev) = max_val - (sum - prev)... Actually: if max was last set to total_sum, before that step it was max_old = max - (total_sum - max).

More precisely: max_old = max % (total_sum - max) (because we can undo multiple additions if the rest sum is much smaller — use modulo for efficiency).

import heapq

def isPossible(target: list[int]) -> bool:
    if len(target) == 1:
        return target[0] == 1
    
    total = sum(target)
    heap = [-x for x in target]  # max-heap via negation
    heapq.heapify(heap)
    
    while True:
        max_val = -heapq.heappop(heap)
        rest = total - max_val
        
        if max_val == 1 or rest == 1:
            return True
        
        if max_val < rest or rest == 0:
            return False
        
        # Undo: what was max_val before? It was set to rest + prev_val.
        # So prev_val = max_val % rest
        new_val = max_val % rest
        if new_val == 0:
            new_val = rest  # avoid infinite loop when max_val is exact multiple
        
        total = rest + new_val
        heapq.heappush(heap, -new_val)
    
    return False

Why Modulo?​

If max_val = 100 and rest = 3, before adding we would have had values like 97, 94, 91... We can undo all these at once with new_val = max_val % rest.

Edge Cases​

  • target = [1] → always true (single-element array must already equal the starting value)
  • target = [2] → false for n=1: with a single-element array, arr starts as [1] and every subsequent operation just sets arr[0] to the current sum, which is always 1 again — it can never become 2
  • Two elements where one is 1 and the sum of the rest is 1 → true (base case [1,1])
  • rest == 0 (all zeros left) with max_val > 1 → false, no way to regenerate a positive value from nothing

Complexity​

  • Time: O(n log n) heap build + O(log(maxVal) × log n) operations
  • Space: O(n) heap

Key Terms​

TermDefinition
Reverse simulationWorking backward from the target state to the known starting state instead of simulating forward
Max-heapA binary heap that gives O(log n) access to the current largest element
Modulo shortcutUsing max_val % rest to collapse many repeated "undo" steps into one operation
GreedyAlways undoing the largest element first, since it must have been the last one modified

FAQ​

Q: Why must we always operate on the largest element? A: Every element other than the largest one was already present, unmodified, when the largest one was last set to the total sum. So the largest value is always the most recently changed one, and reversing it first is the only valid move.

Q: Why use modulo instead of repeatedly subtracting rest? A: If max_val is much larger than rest, repeated subtraction could take O(max_val / rest) steps. Taking max_val % rest in one shot reduces this to O(log(maxVal)) total heap operations.

Q: What causes an early false? A: If max_val < rest (impossible since max_val should be the largest) or rest == 0 while max_val != 1, we can't regenerate a positive next value, so the reconstruction is impossible.

Q: Can this be solved by simulating forward instead? A: No — forward simulation from [1,1,...,1] has no way to know which index to update at each step without already knowing the answer, so it isn't tractable in general.

Q: What's a common implementation bug? A: Forgetting the new_val == 0 correction — when max_val is an exact multiple of rest, the modulo yields 0, but the actual previous value must have been rest itself (an infinite loop otherwise).

Quick Revision​

  • Pattern: greedy reverse simulation using a max-heap.
  • The largest element in target was always the most recently modified one.
  • Reversing it means computing what it was before the last "set to sum" operation.
  • new_val = max_val % rest collapses multiple undo steps into one, where rest = total - max_val.
  • If new_val == 0, use rest instead (avoids infinite loop when max_val is an exact multiple).
  • Terminate with true when max_val == 1 or rest == 1.
  • Terminate with false when max_val < rest or rest == 0 (and max_val != 1).
  • Special-case n == 1: valid only if target[0] == 1.
  • Time: O(n log n) heap build + O(log(maxVal) log n) pop/push cycles.
  • 135 - Candy — another greedy array-reconstruction problem using local constraints
  • 215 - Kth Largest Element in an Array — shares the max-heap technique for repeatedly extracting the largest value
  • Pattern match: any "undo the most recent large operation" problem benefits from the same max-heap + modulo-shortcut approach