370. Range Addition

leetcode medium

#array#csharp#leetcode#medium

Task

Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].

У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.

Верните arr после применения всех обновлений.

Пример:

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

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

C# solution

matched/original

public int[] GetModifiedArray(int length, int[][] updates) {
    int[] result = new int[length];
    foreach (var update in updates) {
        int start = update[0], end = update[1], val = update[2];
        result[start] += val;
        if (end + 1 < length) {
            result[end + 1] -= val;
        }
    }
    for (int i = 1; i < length; i++) {
        result[i] += result[i - 1];
    }
    return result;
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public vector<int>& GetModifiedArray(int length, int[][] updates) {
    vector<int>& result = new int[length];
    foreach (var update in updates) {
        int start = update[0], end = update[1], val = update[2];
        result[start] += val;
        if (end + 1 < length) {
            result[end + 1] -= val;
        }
    }
    for (int i = 1; i < length; i++) {
        result[i] += result[i - 1];
    }
    return result;
}

Java solution

matched/original

public int[] getModifiedArray(int length, int[][] updates) {
    int[] result = new int[length];

    for (int[] update : updates) {
        int start = update[0], end = update[1], val = update[2];
        result[start] += val;
        if (end + 1 < length) {
            result[end + 1] -= val;
        }
    }

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

    return result;
}

JavaScript solution

matched/original

function getModifiedArray(length, updates) {
    let result = new Array(length).fill(0);

    for (let update of updates) {
        let [start, end, val] = update;
        result[start] += val;
        if (end + 1 < length) {
            result[end + 1] -= val;
        }
    }

    for (let i = 1; i < length; i++) {
        result[i] += result[i - 1];
    }

    return result;
}

Python solution

matched/original

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

    for update in updates:
        start, end, val = update
        result[start] += val
        if end + 1 < length:
            result[end + 1] -= val

    for i in range(1, length):
        result[i] += result[i - 1]

    return result

Go solution

matched/original

func getModifiedArray(length int, updates [][]int) []int {
    result := make([]int, length)

    for _, update := range updates {
        start, end, val := update[0], update[1], update[2]
        result[start] += val
        if end+1 < length {
            result[end+1] -= val
        }
    }

    for i := 1; i < length; i++ {
        result[i] += result[i-1]
    }

    return result
}

Explanation

Algorithm

Для каждого обновления (start, end, val) выполните две операции:

Увеличьте значение в позиции start на val: arr[start] = arr[start] + val.

Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val.

Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0).

Верните обновленный массив arr.

😎