LeetCode: Range Addition

Posted on February 15, 2018July 26, 2020 by braindenny

Range Addition

Similar Problems:

Assume you have an array of length n initialized with all 0’s and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

Given:

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

Output:

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

Explanation:

Initial state:
[ 0, 0, 0, 0, 0 ]

After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]

After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]

After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: Initialize array with n+1 length to simplify code

// https://code.dennyzhang.com/range-addition
// Basic Ideas: range update
//
// Complexity: Tiem O(n), Space O(1)
func getModifiedArray(length int, updates [][]int) []int {
    res := make([]int, length+1)
    for _, v := range updates {
        res[v[0]]+=v[2]
        res[v[1]+1]-=v[2]
    }
    for i:=1; i<length; i++ {
        res[i] += res[i-1]
    }
    return res[0:length]
}

Solution

// https://code.dennyzhang.com/range-addition
// Basic Ideas: range update
//
// Complexity: Tiem O(n), Space O(1)
func getModifiedArray(length int, updates [][]int) []int {
    res := make([]int, length)
    for _, v := range updates {
        res[v[0]]+=v[2]
        if v[1]+1 < length {
            res[v[1]+1]-=v[2]
        }
    }
    for i:=1; i<length; i++ {
        res[i] += res[i-1]
    }
    return res
}

## https://code.dennyzhang.com/range-addition
## Basic Ideas:
##
##         0  0  0  0  0  0    ([1, 3, 2])
##         0  2  0  0 -2  0    ([2, 4, 3])
##         0  2  3  0 -2 -3    ([0, 2, -2])
##        -2  2  3  2 -2 -3
## delta: -2  0  3  5  3  0
##
## Complexity: Time O(n+k), Space O(n)
##
class Solution:
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        delta_list = [0] * length
        for [start, end, inc] in updates:
            delta_list[start] += inc
            if end+1 < length:
                delta_list[end+1] -= inc

        delta = 0
        for i in range(0, length):
            delta += delta_list[i]
            delta_list[i] = delta
        return delta_list

Post Views: 8