Output: [0,-4,2,2,2,4,4,-4,-4,-4]

Solution

Method 1 - Using Heap

Here is the approach:

The updates array is sorted by starting index.
A min-heap (priority queue) is used to manage the updates efficiently based on the ending index.
As we traverse the result array, we update the sum by adding the increments starting at current index i and removing increments that end before i.

Code

[{"language":"Java","code":"public class Solution {\n    public int[] getModifiedArray(int length, int[][] updates) {\n        int[] result = new int[length];\n        if (updates == null || updates.length == 0) {\n            return result;\n        }\n\n        // Sort updates by starting index\n        Arrays.sort(updates, Comparator.comparingInt(a -> a[0]));\n\n        // Create a heap sorted by ending index\n        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(a -> updates[a][1]));\n\n        int sum = 0;\n        int j = 0;\n\n        for (int i = 0; i < length; i++) {\n            // Subtract value from sum when ending index is reached\n            while (!queue.isEmpty() && updates[queue.peek()][1] < i) {\n                int top = queue.poll();\n                sum -= updates[top][2];\n            }\n\n            // Add value to sum when starting index is reached\n            while (j < updates.length && updates[j][0] <= i) {\n                sum += updates[j][2];\n                queue.offer(j);\n                j++;\n            }\n\n            result[i] = sum;\n        }\n\n        return result;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#242

Related Tags