Computing Point Counts from a Set of Intervals

Given n points on a line numbered from 1 to n, and a list of intervals, where each interval [l, r, count] adds count to every point from l to r (inclusive). Compute the total count at each point after processing all intervals.

Examples:

Input : n = 5, intervals[] = [[1, 2, 9], [2, 4, 5], [3, 5, 7]]
Output : [9, 14, 12, 12, 7]
Explanation:
Points: 1 2 3 4 5
Interval [1,2,9]: 9 9
Interval [2,4,5]: 5 5 5
Interval [3,5,7]: 7 7 7
Total count: 9 14 12 12 7
Input : n = 4, intervals[] = [[1, 3, 2], [2, 4, 3]]
Output : [2, 5, 5, 3]
Explanation:
Points: 1 2 3 4
Interval [1,3,2]: 2 2 2
Interval [2,4,3]: 3 3 3
Total count: 2 5 5 3

Table of Content

[Naive Approach] Updating Every Point in Each Interval – O(m × n) Time and O(n) Space
[Optimized Approach] Using Prefix Contribution – O(n + m) Time and O(n) Space

[Naive Approach] Updating Every Point in Each Interval – O(m × n) Time and O(n) Space

Process each interval [l, r, count] and add count to every point from l to r in the result array. Initialize an array of size n with 0 and update all elements within each interval.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> intervalContribution(int n, int intervals[][3], int m) {

    vector<int> result(n, 0);

    // Process each interval
    for (int i = 0; i < m; i++) {

        int l = intervals[i][0];
        int r = intervals[i][1];
        int count = intervals[i][2];

        // Update every point in the interval
        for (int j = l - 1; j <= r - 1; j++) {
            result[j] += count;
        }
    }

    return result;
}

int main() {

    int n = 5;

    int intervals[][3] = {
        {1, 2, 9},
        {2, 4, 5},
        {3, 5, 7}
    };

    int m = sizeof(intervals) / sizeof(intervals[0]);

    vector<int> result = intervalContribution(n, intervals, m);

    // Printing result
    for (int i = 0; i < n; i++) {
        cout << result[i] << " ";
    }

    return 0;
}

Java

import java.util.Arrays;
import java.util.Vector;

public class GfG {

    public int[] intervalContribution(int n, int[][] intervals, int m) {

        int[] result = new int[n];
        Arrays.fill(result, 0);

        // Process each interval
        for (int i = 0; i < m; i++) {

            int l = intervals[i][0];
            int r = intervals[i][1];
            int count = intervals[i][2];

            // Update every point in the interval
            for (int j = l - 1; j <= r - 1; j++) {
                result[j] += count;
            }
        }

        return result;
    }

    public static void main(String[] args) {

        int n = 5;

        int[][] intervals = {
            {1, 2, 9},
            {2, 4, 5},
            {3, 5, 7}
        };

        int m = intervals.length;

        GfG obj = new GfG();

        int[] result = obj.intervalContribution(n, intervals, m);

        // Printing result
        for (int i = 0; i < n; i++) {
            System.out.print(result[i] + " ");
        }
    }
}

Python

def intervalContribution(n, intervals):

    result = [0] * n

    # Process each interval
    for i in range(len(intervals)):

        l = intervals[i][0]
        r = intervals[i][1]
        count = intervals[i][2]

        # Update every point in the interval
        for j in range(l - 1, r):
            result[j] += count

    return result


if __name__ == "__main__":

    n = 5

    intervals = [
        [1, 2, 9],
        [2, 4, 5],
        [3, 5, 7]
    ]

    result = intervalContribution(n, intervals)

    # Printing result
    for value in result:
        print(value, end=" ")

using System;

public class GfG {

    public int[] IntervalContribution(int n, int[,] intervals, int m) {

        int[] result = new int[n];

        // Process each interval
        for (int i = 0; i < m; i++) {

            int l = intervals[i, 0];
            int r = intervals[i, 1];
            int count = intervals[i, 2];

            // Update every point in the interval
            for (int j = l - 1; j <= r - 1; j++) {
                result[j] += count;
            }
        }

        return result;
    }

    public static void Main() {

        int n = 5;

        int[,] intervals = {
            {1, 2, 9},
            {2, 4, 5},
            {3, 5, 7}
        };

        int m = intervals.GetLength(0);

        GfG obj = new GfG();

        int[] result = obj.IntervalContribution(n, intervals, m);

        // Printing result
        foreach (int i in result) {
            Console.Write(i + " ");
        }
    }
}

JavaScript

function intervalContribution(n, intervals, m) {

    let result = Array(n).fill(0);

    // Process each interval
    for (let i = 0; i < m; i++) {

        let l = intervals[i][0];
        let r = intervals[i][1];
        let count = intervals[i][2];

        // Update every point in the interval
        for (let j = l - 1; j <= r - 1; j++) {
            result[j] += count;
        }
    }

    return result;
}

let n = 5;

let intervals = [
    [1, 2, 9],
    [2, 4, 5],
    [3, 5, 7]
];

let m = intervals.length;

let result = intervalContribution(n, intervals, m);

// Printing result
for (let i = 0; i < n; i++)
    console.log(result[i]);

Output

9 14 12 12 7

[Optimized Approach] Using Prefix Contribution – O(n + m) Time and O(n) Space

For each interval [l, r, count], add count at index l − 1 and subtract count at index r (if it is within bounds). After processing all intervals, compute the prefix sum of the array to propagate the contributions and obtain the final count at each point.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> intervalContribution(int n, int intervals[][3], int m) {

    vector<int> diff(n + 1, 0);

    // Mark start and end of contributions
    for (int i = 0; i < m; i++) {

        int l = intervals[i][0];
        int r = intervals[i][1];
        int count = intervals[i][2];

        diff[l - 1] += count;

        if (r < n)
            diff[r] -= count;
    }

    // Build final result using prefix sum
    vector<int> result(n);
    result[0] = diff[0];

    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] + diff[i];
    }

    return result;
}

int main() {

    int n = 5;

    int intervals[][3] = {
        {1, 2, 9},
        {2, 4, 5},
        {3, 5, 7}
    };

    int m = sizeof(intervals) / sizeof(intervals[0]);

    vector<int> result = intervalContribution(n, intervals, m);

    // Printing result
    for (int i = 0; i < n; i++) {
        cout << result[i] << " ";
    }

    return 0;
}