Construct Target Array With Multiple Sums

Hard

#1257Time: O(K * N), where N is the length of the array and K is the number of backward steps. K can be very large, proportional to the maximum value in `target`, making this solution too slow.Space: O(1) if the input array is modified in-place. O(N) if a copy of the array is used.1 company

Data structures

Array Heap (Priority Queue)

Companies

Quora

Prompt

You are given an array target of n integers. From a starting array arr consisting of n 1's, 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 set the value of arr at index i 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: Start with arr = [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Constraints:

n == target.length
1 <= n <= 5 * 10⁴
1 <= target[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process in reverse, starting from the target array and trying to reach the initial [1, 1, ..., 1] array. The logic is that the largest element in the current array must have been the one generated in the last step. We can undo this step by subtracting the sum of the other elements from this largest element. We repeat this process until all elements become 1. To find the largest element at each step, we perform a linear scan of the array.

Algorithm

The core idea is to work backward from the target array to the initial array of all ones. The forward process involves replacing an element arr[i] with the sum of all elements. This implies that at any step, the largest element in the array must have been the one that was just created. We can reverse this process:

Start a loop that continues as long as the largest element in the array is greater than 1.
In each iteration, find the largest element maxVal and its index maxIdx by scanning the array.
Calculate the sum of all other elements, restSum.
The value of the element at maxIdx before this step must have been prevVal = maxVal - restSum.
Check for invalid states:
- If maxVal <= restSum, then prevVal would be less than or equal to 0. Since we start with all 1s and only add positive numbers, all elements must always be positive. This is an impossible state, so we return false.
- If restSum is 0 (and n > 1), it's also impossible as all elements must be at least 1.
Update the array by setting the element at maxIdx to prevVal.
If the loop completes, it means the largest element is 1, which implies all elements are 1. We have successfully reached the starting state, so we return true.

Walkthrough

This method is a direct implementation of the backward simulation logic. While it's conceptually simple, its performance is poor due to the repeated linear scans and the potentially large number of steps required to reduce the target values to 1.

For example, if target = [1, 10^9], the process would be: [1, 10^9] -> [1, 10^9 - 1] -> [1, 10^9 - 2] ... This would require nearly 10^9 steps, each involving a scan of the array, making it infeasible.

1class Solution {2    public boolean isPossible(int[] target) {3        if (target.length == 1) {4            return target[0] == 1;5        }6 7        long sum = 0;8        for (int val : target) {9            sum += val;10        }11 12        while (true) {13            int maxIdx = -1;14            int maxVal = -1;15            for (int i = 0; i < target.length; i++) {16                if (target[i] > maxVal) {17                    maxVal = target[i];18                    maxIdx = i;19                }20            }21 22            if (maxVal == 1) {23                return true; // All elements are 124            }25 26            long restSum = sum - maxVal;27 28            if (restSum == 0 || maxVal <= restSum) {29                return false;30            }31 32            int prevVal = (int) (maxVal - restSum);33            if (prevVal < 1) {34                return false;35            }36 37            sum = sum - maxVal + prevVal;38            target[maxIdx] = prevVal;39        }40    }41}

Complexity

Time

O(K * N), where N is the length of the array and K is the number of backward steps. K can be very large, proportional to the maximum value in `target`, making this solution too slow.

Space

O(1) if the input array is modified in-place. O(N) if a copy of the array is used.

Trade-offs

Pros

Simple to understand and reason about.
Low space complexity as it can modify the array in-place.

Cons

Extremely inefficient for large input values as the numbers decrease by a small amount in each step.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.

This approach significantly improves the backward simulation by using a max-heap to efficiently find the largest element and employing modulo arithmetic to bypass a large number of redundant subtraction steps. By replacing maxVal with maxVal % restSum, we can reduce large numbers to a value smaller than the second-largest element in just one operation, drastically cutting down the number of iterations needed.

Algorithm

This optimized approach also works backward but addresses the two main inefficiencies of the brute-force method.

Finding the Maximum: Instead of a linear scan, a max-heap (implemented as a PriorityQueue in Java) is used. This allows us to retrieve the maximum element in O(log N) time.
Reducing Large Numbers: When the largest element maxVal is significantly larger than the sum of the rest restSum, repeatedly subtracting restSum is slow. This series of subtractions is equivalent to the modulo operation. The new value can be calculated in one step as prevVal = maxVal % restSum.

The Algorithm:

Handle edge cases: If n=1, return true only if target[0] == 1.
Calculate the total sum of elements (using a long to avoid overflow) and push all elements into a max-heap.
Loop as long as the top element of the heap is greater than 1.
In each iteration: a. Pop the largest element maxVal from the heap. b. Calculate restSum = sum - maxVal. c. Check for failure/termination conditions: i. If restSum == 1, it means all other elements are 1s. We can always reduce maxVal to 1 by subtracting 1 repeatedly. So, we can return true. ii. If maxVal <= restSum or restSum == 0, the state is invalid. Return false. d. Calculate the previous value using the modulo optimization: prevVal = maxVal % restSum. e. If prevVal is 0 (which happens if maxVal is a multiple of restSum), it's an impossible state because restSum > 1 at this point. Return false. f. Insert prevVal back into the heap. g. Update the total sum: sum = restSum + prevVal.
If the loop completes, all elements are 1. Return true.

Walkthrough

The use of a max-heap reduces the time to find the maximum element from O(N) to O(log N). The modulo arithmetic is the key optimization for performance. If we have a state like [100, 3], the sum is 103, maxVal is 100, and restSum is 3. Instead of doing 100-3=97, 97-3=94, etc., we can directly compute the new value as 100 % 3 = 1. This transforms the array to [1, 3] in a single step, which is much faster.

1import java.util.PriorityQueue;2import java.util.Collections;3 4class Solution {5    public boolean isPossible(int[] target) {6        // Handle edge case for n=17        if (target.length == 1) {8            return target[0] == 1;9        }10 11        // Use a max-heap to easily access the largest element12        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());13        long sum = 0;14        for (int num : target) {15            sum += num;16            maxHeap.add(num);17        }18 19        // Work backwards from the target20        while (maxHeap.peek() > 1) {21            int maxVal = maxHeap.poll();22            long restSum = sum - maxVal;23 24            // If restSum is 1, we can always form the target.25            // The other n-1 elements are 1s, and we can reduce maxVal to 126            // by repeatedly subtracting 1 (the restSum).27            if (restSum == 1) {28                return true;29            }30 31            // If maxVal is smaller than or equal to the rest, we can't go back.32            // prevVal = maxVal - restSum would be <= 0.33            // restSum can't be 0 if n > 1 and all elements are positive.34            if (maxVal <= restSum || restSum == 0) {35                return false;36            }37 38            // Use modulo to perform multiple subtractions at once39            int prevVal = (int) (maxVal % restSum);40 41            // If maxVal is a multiple of restSum, prevVal becomes 0, which is invalid.42            // This is only possible if the previous element was also a multiple of restSum,43            // which can't be true starting from 1s.44            if (prevVal == 0) {45                return false;46            }47 48            // Update sum and add the new element to the heap49            sum = restSum + prevVal;50            maxHeap.add(prevVal);51        }52 53        // If we reach here, all elements are 1s54        return true;55    }56}

Complexity

Time

O(N + log(M) * log(N)), where N is the array size and M is the maximum element in `target`. O(N) is for building the heap. The number of loop iterations is logarithmic with respect to M due to the modulo operation, and each iteration costs O(log N) for heap operations.

Space

O(N), where N is the length of the `target` array, for storing the elements in the priority queue.

Trade-offs

Pros

Highly efficient and passes within the time limits for large inputs.
Correctly handles edge cases and large numbers using modulo arithmetic.

Cons

Requires more complex data structures (a heap).
Uses more space to store the elements in the heap.

Solutions

Solution

1class Solution {2public3  boolean isPossible(int[] target) {4    PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());5    long s = 0;6    for (int x : target) {7      s += x;8      pq.offer((long)x);9    }10    while (pq.peek() > 1) {11      long mx = pq.poll();12      long t = s - mx;13      if (t == 0 || mx - t < 1) {14        return false;15      }16      long x = mx % t;17      if (x == 0) {18        x = t;19      }20      pq.offer(x);21      s = s - mx + x;22    }23    return true;24  }25}

1class Solution {2public:3  bool isPossible(vector<int> &target) {4    priority_queue<int> pq;5    long long s = 0;6    for (int i = 0; i < target.size(); i++) {7      s += target[i];8      pq.push(target[i]);9    }10    while (pq.top() != 1) {11      int mx = pq.top();12      pq.pop();13      long long t = s - mx;14      if (t < 1 || mx - t < 1) {15        return false;16      }17      int x = mx % t;18      if (x == 0) {19        x = t;20      }21      pq.push(x);22      s = s - mx + x;23    }24    return true;25  }26};

1class Solution:2    def isPossible(self, target: List[int]) -> bool: s = sum(target) pq = [- x for x in target] heapify(pq) while - pq[0] > 1: mx = - heappop(pq) t = s - mx if t == 0 or mx - t < 1: return False x = (mx % t) or t heappush(pq, - x) s = s - mx + x return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem