HardNo. 1354
Construct Target Array With Multiple Sums — LeetCode 1354 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Heap (Priority Queue)
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- target = [9,3,5]
- Output
- true
- Explanation
- Start with arr = [1, 1, 1]
Python solution
class Solution:
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 TrueComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(n)where n is the length of array target
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1354. Construct Target Array With Multiple Sums is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0215 | Kth Largest Element in an Array | Medium |
| 0218 | The Skyline Problem | Hard |
| 0373 | Find K Pairs with Smallest Sums | Medium |
| 0407 | Trapping Rain Water II | Hard |
| 0506 | Relative Ranks | Easy |
| 0675 | Cut Off Trees for Golf Event | Hard |
Frequently asked questions
- How hard is LeetCode 1354. Construct Target Array With Multiple Sums?
LeetCode 1354. Construct Target Array With Multiple Sums is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1354. Construct Target Array With Multiple Sums?
The Python solution on this page runs in O(n log n).
- What is the space complexity of LeetCode 1354. Construct Target Array With Multiple Sums?
The Python solution on this page uses O(n), where n is the length of array \textit{target} auxiliary space.
- What topics does LeetCode 1354. Construct Target Array With Multiple Sums cover?
LeetCode 1354. Construct Target Array With Multiple Sums is tagged Array and Heap (Priority Queue) on LeetCode.