Skip to content

Commit 99d00b6

Browse files
refactor 1354
1 parent fbf26da commit 99d00b6

File tree

1 file changed

+1
-33
lines changed

1 file changed

+1
-33
lines changed

src/main/java/com/fishercoder/solutions/_1354.java

Lines changed: 1 addition & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -3,45 +3,13 @@
33
import java.util.Collections;
44
import java.util.PriorityQueue;
55

6-
/**
7-
* 1354. Construct Target Array With Multiple Sums
8-
*
9-
* Given an array of integers target. From a starting array, A consisting of all 1's, you may perform the following procedure :
10-
* let x be the sum of all elements currently in your array.
11-
* choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
12-
* You may repeat this procedure as many times as needed.
13-
* Return True if it is possible to construct the target array from A otherwise return False.
14-
*
15-
* Example 1:
16-
* Input: target = [9,3,5]
17-
* Output: true
18-
* Explanation: Start with [1, 1, 1]
19-
* [1, 1, 1], sum = 3 choose index 1
20-
* [1, 3, 1], sum = 5 choose index 2
21-
* [1, 3, 5], sum = 9 choose index 0
22-
* [9, 3, 5] Done
23-
*
24-
* Example 2:
25-
* Input: target = [1,1,1,2]
26-
* Output: false
27-
* Explanation: Impossible to create target array from [1,1,1,1].
28-
*
29-
* Example 3:
30-
* Input: target = [8,5]
31-
* Output: true
32-
*
33-
* Constraints:
34-
* N == target.length
35-
* 1 <= target.length <= 5 * 10^4
36-
* 1 <= target[i] <= 10^9
37-
* */
386
public class _1354 {
397
public static class Solution1 {
408
/**
419
* 1. A good idea/trick to calculate the previous value of the largest number max: (2 * max - total).
4210
* 2. Use a PriorityQueue to store the elements in reverse order to help us get the largest element in O(1) time
4311
* 3. Also keep a variable of total sum
44-
*
12+
* <p>
4513
* reference: https://leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/510214/C%2B%2B-Reaching-Points-Work-Backwards
4614
*/
4715
public boolean isPossible(int[] target) {

0 commit comments

Comments
 (0)