# Hard: Array manipulation

2 min read Tweet this post
Section titled Problem%20Statement

## Problem Statement

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Example:

$n=10\\queries = [[1,5,3],[4,8,7],[6,9,1]]$

Queries are interpreted as follows:

    a b k
1 5 3
4 8 7
6 9 1


Add the values of $k$ between the indices $a$ and $b$ inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]


The larges values is $10$ after all operation are performed.

Section titled Solution

## Solution

Section titled Brute%20Force

### Brute Force

• Create array with length n+1 to simplify update result
• For each queries sum index range from a to b with values of k
• Find max values
func arrayManipulation(n int32, queries [][]int32) int64 {
result:=make([]int64, n+1)

for _, q:= range queries{
for from:=q[0];from<=q[1];from++{
result[from]+=int64(q[2])
}
}
// fmt.Println(result)
max:=int64(-1)
for _,q:= range result{
if max < q{
max = q
}
}

return int64(max)
}



This solution works well with small data test, but got time limit exceeded with the data growing big because we must iterate from a to b every query.

Section titled Prefix-sum1

### Prefix-sum1

• The process starts by initializing an array of size n with all zeros. Then, the function processes each query in the two-dimensional array of queries. Each query is a triplet of integers (a, b, k) that represents adding the value k to all elements in the range [a, b] of the array arr.
• To perform this operation efficiently, the function uses the technique of prefix sums1 (cumulative sums), where each element of the array represents the difference between the current element and the previous one. This technique allows us to compute the sum of a range of elements in the array in constant time.
• After processing all the queries, the function loops through the array and computes the maximum value by keeping track of the running sum of the array elements. The maximum value is updated whenever the running sum exceeds the current maximum.
func arrayManipulation(n int32, queries [][]int32) int64 {
arr := make([]int64, n)
for _, q := range queries {
a, b, k := q[0], q[1], q[2]
arr[a-1] += int64(k)
if b < n {
arr[b] -= int64(k)
}
}
max := int64(0)
sum := int64(0)
for _, val := range arr {
sum += val
if sum > max {
max = sum
}
}
return max
}

Section titled Dry%20Run

### Dry Run

• Sample Input
5 3
1 2 100
2 5 100
3 4 100

• initial array: [ 0, 0, 0, 0, 0]

• q[0], 1 2 100 : [ 100, 0,-100, 0, 0]

• q[1], 2 5 100 : [ 100, 100,-100, 0, 0], add -100 skipped because b is same with n

• q[3], 3 4 100 : [ 100, 100, 0, 0,-100]

• find the max values from current sum

• index 0 : sum = 100, max = 100, max updated
• index 1 : sum = 200, max = 200, max updated
• index 2 : sum = 200, max = 200
• index 3 : sum = 200, max = 200
• index 4 : sum = 100, max = 200
• final result is $200$

Section titled Footnotes

## Footnotes

grokking algorithm go prefix-sum