Hard: Array manipulation

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:

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.

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

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.

Prefix-sum¹

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 sums¹ (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
}

Dry Run

Sample Input

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$

Prefix Sum https://www.dcc.fc.up.pt/~pribeiro/aulas/pc2021/material/prefixsums.html ↩ ↩²

Problem Statement

Solution

Brute Force

Prefix-sum1

Dry Run

Footnotes

Prefix-sum¹