Published on

# Hard: Array manipulation

Authors
• Name
Moch Lutfi
@kaptenupi

## 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:

_4 a b k_4 1 5 3_4 4 8 7_4 6 9 1

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

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

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

## Solution

### 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
_18func arrayManipulation(n int32, queries [][]int32) int64 {_18 result:=make([]int64, n+1)_18 _18 for _, q:= range queries{_18 for from:=q;from<=q;from++{_18 result[from]+=int64(q)_18 }_18 }_18 // fmt.Println(result)_18 max:=int64(-1)_18 for _,q:= range result{_18 if max < q{_18 max = q_18 }_18 }_18 _18 return int64(max)_18}

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.

### 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.
_19func arrayManipulation(n int32, queries [][]int32) int64 {_19 arr := make([]int64, n)_19 for _, q := range queries {_19 a, b, k := q, q, q_19 arr[a-1] += int64(k)_19 if b < n {_19 arr[b] -= int64(k)_19 }_19 }_19 max := int64(0)_19 sum := int64(0)_19 for _, val := range arr {_19 sum += val_19 if sum > max {_19 max = sum_19 }_19 }_19 return max_19}

### Dry Run

• Sample Input
_45 3_41 2 100_42 5 100_43 4 100
• initial array: [ 0, 0, 0, 0, 0]

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

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

• q, 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$