leetcode/zero_array_transformation_II.js at main · p-lurd/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
var minZeroArray = function(nums, queries) {
    let diff = Array(nums.length + 1).fill(0)
    for(const [l, r, val] of queries){
        diff[l] += val;
        if( r+1 > nums.length){
            diff[r+1] -= val;
        }
    }
    let newNums = nums;
    let newDiff = diff
    newNums.sort();
    let maxNum = newNums[nums.length - 1];
    newDiff.sort();
    console.log({newDiff})
    let maxDiff = newDiff[nums.length - 1];
    console.log({maxDiff, maxNum});
    if(maxNum <= maxDiff){
        return maxNum;
    }else{
        return -1;
    }
//     let curr = 0;
//     for(let i = 1; i<n; i++){
//         curr -= diff[i];
//         nums[i] += curr;
//         if(nums[i]<0){
//             nums[i] = 0;
//         }
//     }
//     if(nums.every((num) => num < 1)){
//     return diff.max()
//   }
};

// console.log(minZeroArray([2,0,2],[[0,2,1],[0,2,1],[1,1,3]]))


//........................An Optimised Solution
var minZeroArray = function (nums, queries) {
    const diff = Array(nums.length + 1).fill(0); // Initialize diff array

    // Populate the difference array
    for (const [l, r, val] of queries) {
        diff[l] += val;
        if (r + 1 < diff.length) {
            diff[r + 1] -= val;
        }
    }

    // Find max values directly from nums and diff without extra sorting
    const maxNum = Math.max(...nums);
    let curr = 0, maxDiff = 0;

    maxDiff = Math.max(...diff);

    // for (let i = 0; i < nums.length; i++) {
    //     curr += diff[i]; // Apply cumulative updates
    //     maxDiff = Math.max(maxDiff, curr); // Track max diff value
    // }

    // Check if maxNum can be reduced to zero using maxDiff
    return maxNum <= maxDiff ? maxNum : -1;
};


var minZeroArray = function(nums, queries) {
    let diff = Array(nums.length + 1).fill(0);

    for (let queryIndex = 0; queryIndex < queries.length; queryIndex++) {
        const [l, r, val] = queries[queryIndex];
        diff[l] += val;
        if (r + 1 < diff.length) {
            diff[r + 1] -= val;
        }
        let curr = 0;
        for (let i = 0; i < nums.length; i++) {
            curr += diff[i];
            nums[i] += curr;
        }
        if (nums.every((num) => num < 1)) {
            return queryIndex + 1;
        }
    }

    return -1;
};


var minZeroArray = function (nums, queries) {
    const diff = Array(nums.length + 1).fill(0);

    // Apply queries incrementally
    for (let queryIndex = 0; queryIndex < queries.length; queryIndex++) {
        const [l, r, val] = queries[queryIndex];
        diff[l] -= val;
        if (r + 1 < diff.length) {
            diff[r + 1] += val;
        }

        // Use the difference array to update nums incrementally
        let curr = 0;
        for (let i = 0; i < nums.length; i++) {
            curr += diff[i];
            nums[i] += curr;
            if (nums[i] < 0) {
                nums[i] = 0;
            }
        }

        // Check if nums is a zero array
        if (nums.every((num) => num === 0)) {
            return queryIndex + 1; // Return the number of queries ran
        }
    }

    return -1; // Return -1 if nums cannot be made a zero array
};