Range Addition - rFronteddu/general_wiki GitHub Wiki

You are given:

  • An integer length
  • A list of updates, where each update is of the form:
    • [startIndex, endIndex, inc]

Problem Description

  • You have an array arr of size length, initially filled with 0s. For each update [startIndex, endIndex, inc], you must:
    • Add inc to every element in arr from index startIndex to endIndex inclusive.
    • After applying all updates, return the final modified array.

Input

  • int length
  • int[][] updates

Where:

  • 0 <= startIndex <= endIndex < length
  • -10^5 <= inc <= 10^5

Output

  • Return the final array after applying all updates.

Example 1

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

Explanation

Start with:

[0, 0, 0, 0, 0]

After [1,3,2]:

[0, 2, 2, 2, 0]

After [2,4,3]:

[0, 2, 5, 5, 3]

After [0,2,-2]:

[-2, 0, 3, 5, 3]
Output
[-2, 0, 3, 5, 3]

Example 2

Input
length = 3
updates = [
  [0, 2, 1],
  [0, 2, 2]
]
Output
[3, 3, 3]

Constraints

  • 1 <= length <= 10^5
  • 0 <= updates.length <= 10^4
import java.util.*;

class Main {
    
    static int[] solve (int[][] updates,int len) {
        List<int[]> events = new ArrayList<>();
         // O(nlogn)
        for(var u : updates) {
            events.add(new int[]{u[0], u[2]});
            events.add(new int[]{u[1] + 1, -u[2]});
        }
        events.sort(Comparator.comparingInt(a -> a[0]));
        
        int[] out = new int[len];
        int count = 0;
        int eventP = 0;
        for(int i = 0; i < len; i++) {
            // need to process all events that happen at i
            while(eventP < events.size() && events.get(eventP)[0] == i) {
                count += events.get(eventP)[1];
                eventP++;
            }
            out[i] = count;
        }
        
        return out;
    }
    
    public static void main(String[] args) {
        int[][] t1 = { {1,3,2} };
        int len1 = 5;
        int[] ans1 = {0,2,2,2,0};

        // Test 2 — Multiple Overlapping Ranges
        int[][] t2 = {
            {1,3,2},
            {2,4,3}
        };
        int len2 = 6;
        int[] ans2 = {0,2,5,5,3,0};

        // Test 3 — Full Range Update
        int[][] t3 = {
            {0,4,1}
        };
        int len3 = 5;
        int[] ans3 = {1,1,1,1,1};

        // Test 4 — Multiple Same Start
        int[][] t4 = {
            {1,2,3},
            {1,2,2},
            {1,2,5}
        };
        int len4 = 5;
        int[] ans4 = {0,10,10,0,0};

        // Test 5 — Sparse Non-Overlapping
        int[][] t5 = {
            {0,0,4},
            {2,2,7},
            {4,4,3}
        };
        int len5 = 6;
        int[] ans5 = {4,0,7,0,3,0};

        // Test 6 — Negative Updates
        int[][] t6 = {
            {1,3,5},
            {2,2,-3}
        };
        int len6 = 5;
        int[] ans6 = {0,5,2,5,0};

        // Optional: Empty Case
        int[][] t7 = {};
        int len7 = 4;
        int[] ans7 = {0,0,0,0};

        // Example of running one test:
        System.out.println(Arrays.equals(solve(t1, len1), ans1));
        System.out.println(Arrays.equals(solve(t2, len2), ans2));
        System.out.println(Arrays.equals(solve(t3, len3), ans3));
        System.out.println(Arrays.equals(solve(t4, len4), ans4));
        System.out.println(Arrays.equals(solve(t5, len5), ans5));
        System.out.println(Arrays.equals(solve(t6, len6), ans6));
        System.out.println(Arrays.equals(solve(t7, len7), ans7));
       
    }
}
⚠️ **GitHub.com Fallback** ⚠️