Array Manipulation · Coding Gym

Solutions

The brute force solution consists in adding the specified value to each of the given ranges and finally finding the maximum value. Evidently, the complexity of this solution is \( O(N \cdot M)\) (where \(N\) is the size of the array and \(M\) is the number of queries) which is too high to meet time constraints.

A better solution is linear on N and allocates \(O(N)\) space, involving adding the specified value solely to the starting endpoint of the ranges and subtracting it from the position immediately after the ending endpoint. For example:

Here is the starting array:

1
2


1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0

In the first update, we add 3 to [1, 5]. We only do this at the beginning of the range:

1
2


1 2 3 4 5 6 7 8 9 10
3 0 0 0 0 0 0 0 0 0

At the same time, we subtract 3 from the position 5+1=6:

1
2


1 2 3 4 5 6 7 8 9 10
3 0 0 0 0 -3 0 0 0 0

Same story for the rest of the second update:

1
2


1 2 3 4 5 6  7 8 9  10
3 0 0 7 0 -3 0 0 -7 0

And the last one:

1
2


1 2 3 4 5 6  7 8 9  10
3 0 0 7 0 -2 0 0 -7 -1

At this point, we calculate the prefix sum (partial sum) or the whole array:

1

3 3 3 10 10 8 8 8 1 0

Voilà! Is this outcome identical to what we would achieve manually? Yes!

Then the answer is just the maximum of this array, that is 10.

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


long arrayManipulation(int n, const std::vector<std::vector<int>>& queries) 
{
    vector<long long> arr(n+1);
    for (const auto& q : queries)
    {
        arr[q[0]-1] += q[2];
        arr[q[1]] -= q[2];
    }
    partial_sum(begin(arr), end(arr), begin(arr));
    return *max_element(begin(arr), end(arr));
}

It’s worth noting that to elegantly handle the scenario where the ending endpoint equals n, we simply create an array of size n+1.

Using ranges, the prefix sum and the maximum are fluently combined into a single iteration:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


long arrayManipulation(int n, const std::vector<std::vector<int>>& queries) 
{
    std::vector<long long> arr(n+1);
    for (const auto& q : queries)
    {
        arr[q[0]-1] += q[2];
        arr[q[1]] -= q[2];
    }
    return max(views::partial_sum(arr));
}

The rationale behind this solution is straightforward: whenever a value is added between two endpoints, it spreads from the starting index to the ending index (inclusive), but it then “rollbacks” afterward. Therefore, we can efficiently add and combine these “promised propagations” only. Finally, we execute all the “propagations” by running the partial sum that is a single linear step.

Amortized space solution

We notice the biggest element is always at the boundaries of a range, this means we can ignore elements in the middle. Indeed, following the “propagation” idea, we know that elements in the middle of a propagation do not contribute at all to change its contribution.

The idea is to store pairs representing each range contribution instead of modifying the whole array of size N. Each pair is made of the query index and the query value.

Then we sort the array as it wouldn’t make any sense to calculate propagations out of order (alternatively we can use a sorted data structure such as a map), and finally we calculate the partial sum on the values of the sorted array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


long arrayManipulation(int n, const std::vector<std::vector<int>>& queries) 
{
    std::vector<std::pair<int, long>> arr;
    for (const auto& q : queries)
    {
        arr.emplace_back(q[0], q[2]);
        arr.emplace_back(q[1]+1, -q[2]);
    }
    sort(arr);
    return max(arr | views::values | views::partial_sum);
}

Without using ranges, the solution is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


long arrayManipulation(int n, const vector<vector<int>>& queries) 
{
    vector<pair<int, int>> arr;
    for (const auto& q : queries)
    {
        arr.emplace_back(q[0], q[2]);
        arr.emplace_back(q[1]+1, -q[2]);
    }
    sort(begin(arr), end(arr));
    long curr_max = 0;
    long sum = 0;
    for (const auto& [i, j] : arr)
    {
        sum += j;
        curr_max = max(curr_max, sum);
    }
    return curr_max;
}

Overall, the time complexity is \( O(M \cdot logM) \) and the space is \(O(M)\) that might be convenient as we know the number of queries is less than the size of the array.

prefix sum patterns