Problem

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

Examples

Example 1:

$$ \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \end{bmatrix} \implies \begin{bmatrix} 0 & \colorbox{blue} 2 & \colorbox{blue}2 & \colorbox{blue}2 & 0 \end{bmatrix} \implies $$ $$ \begin{bmatrix} 0 & 2 & \colorbox{blue} 5 & \colorbox{blue} 5 & \colorbox{blue}3 \end{bmatrix} \implies \begin{bmatrix} \colorbox{blue} {-2} & \colorbox{blue} 0 & \colorbox{blue} 3 & 5 & 3 \end{bmatrix} $$

1
2

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

Example 2:

1
2

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
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

 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


public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        if (updates == null || updates.length == 0) {
            return result;
        }

        // Sort updates by starting index
        Arrays.sort(updates, Comparator.comparingInt(a -> a[0]));

        // Create a heap sorted by ending index
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(a -> updates[a][1]));

        int sum = 0;
        int j = 0;

        for (int i = 0; i < length; i++) {
            // Subtract value from sum when ending index is reached
            while (!queue.isEmpty() && updates[queue.peek()][1] < i) {
                int top = queue.poll();
                sum -= updates[top][2];
            }

            // Add value to sum when starting index is reached
            while (j < updates.length && updates[j][0] <= i) {
                sum += updates[j][2];
                queue.offer(j);
                j++;
            }

            result[i] = sum;
        }

        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def getModifiedArray(self: length, updates):
        result = [0] * length

        updates.sort(key=lambda x: x[0])

        heap = []
        sum_val = 0
        j = 0

        for i in range(length):
            while heap and heap[0][0] < i:
                _, inc = heappop(heap)
                sum_val -= inc

            while j < len(updates) and updates[j][0] <= i:
                heappush(heap, (updates[j][1], updates[j][2]))
                sum_val += updates[j][2]
                j += 1

            result[i] = sum_val

        return result

Complexity

  • ⏰ Time complexity: O(n log m),  where n is the length of the array and m is the number of updates. Sorting the updates costs O(m log m) and each element is processed through the heap operations, costing O(n log m) in total.
  • 🧺 Space complexity: O(m), due to the space used by the heap to store the indices of the updates being processed.

Method 2 - Using Prefix Sum

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] arr = new int[length];
        
        for (int[] update : updates) {
            int startIdx = update[0];
            int endIdx = update[1];
            int inc = update[2];
            
            arr[startIdx] += inc;
            if (endIdx + 1 < length) {
                arr[endIdx + 1] -= inc;
            }
        }
        
        int currentSum = 0;
        for (int i = 0; i < length; i++) {
            currentSum += arr[i];
            arr[i] = currentSum;
        }
        
        return arr;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def getModifiedArray(length, updates):
    arr = [0] * length

    for update in updates:
        startIdx, endIdx, inc = update
        arr[startIdx] += inc
        if endIdx + 1 < length:
            arr[endIdx + 1] -= inc

    current_sum = 0
    for i in range(length):
        current_sum += arr[i]
        arr[i] = current_sum

    return arr

Complexity

  • ⏰ Time complexity: O(n + m), , where n is the length of arr and m is the number of updates. This is because we iterate over the updates once and then compute the prefix sum in another pass.
  • 🧺 Space complexity: O(1), extra space (excluding the input and output arrays).