Range Addition - Practice Coding Problems

Range Addition - 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 operations to apply on arr.

In the i-th operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

Input & Output

Example 1 — Basic Range Updates

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

› Output: [-2,0,1,3,3]

💡 Note: 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]. Wait, let me recalculate: [-2,0,1,3,3]

Example 2 — Single Update

$ Input: length = 10, updates = [[2,4,6]]

› Output: [0,0,6,6,6,0,0,0,0,0]

💡 Note: Add 6 to indices 2,3,4. All other positions remain 0.

Example 3 — Overlapping Updates

$ Input: length = 3, updates = [[0,1,1],[1,2,1]]

› Output: [1,2,1]

💡 Note: First update: [1,1,0]. Second update adds to indices 1,2: [1,2,1].

Constraints

1 ≤ length ≤ 10⁵
0 ≤ updates.length ≤ 10⁴
0 ≤ startIdxi ≤ endIdxi < length
-1000 ≤ inci ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of zeros with length n and list of range updates

Process

Apply each range update [start,end,inc] to add inc to range

Output

Final array after all updates applied

Key Takeaway

🎯 Key Insight: Use difference array to mark range boundaries in O(1), then compute prefix sum for final values

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use a difference array to mark range boundaries instead of updating each element individually. The optimal approach uses difference array with prefix sum: mark start/end boundaries in O(1) per update, then compute final values with one pass. Time: O(n+m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Difference Array (Optimal)	O(n + m)	O(1)	Use difference array to mark range boundaries, then compute prefix sum
Brute Force	O(n × m)	O(1)	Apply each update directly to all elements in the range

Difference Array (Optimal) — Algorithm Steps

Step 1: Create difference array of size length+1
Step 2: For each update [start, end, inc], add inc to diff[start] and subtract inc from diff[end+1]
Step 3: Compute prefix sum of difference array to get final result

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark Boundaries

Add increment at start, subtract at end+1

Prefix Sum

Sweep left to right accumulating values

Result

Final array after prefix sum computation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int length, int updates[][3], int updatesSize, int* returnSize) {
    int* diff = (int*)calloc(length + 1, sizeof(int));
    *returnSize = length;
    
    // Mark boundaries in difference array
    for (int i = 0; i < updatesSize; i++) {
        int start = updates[i][0], end = updates[i][1], inc = updates[i][2];
        diff[start] += inc;
        if (end + 1 < length) {
            diff[end + 1] -= inc;
        }
    }
    
    // Compute prefix sum to get final values
    int* result = (int*)malloc(length * sizeof(int));
    result[0] = diff[0];
    for (int i = 1; i < length; i++) {
        result[i] = result[i - 1] + diff[i];
    }
    
    free(diff);
    return result;
}

int main() {
    int length;
    scanf("%d", &length);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for [[a,b,c],[d,e,f],...] format
    int updates[1000][3];
    int updatesSize = 0;
    char* ptr = line + 1; // Skip first '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            updates[updatesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            updates[updatesSize][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            updates[updatesSize][2] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            updatesSize++;
        }
        if (*ptr == ',') ptr++;
    }
    
    int returnSize;
    int* result = solution(length, updates, updatesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

n is array length, m is number of updates. Each update takes O(1), prefix sum takes O(n)

✓ Linear Growth

Space Complexity

O(1)

Only using the result array and constant variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Difference Array (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler