Quick Links

### Problem Statement of Array Manipulation

Suppose you are given with an array filled with all zeroes initially and Q queries. In each of the Q queries, you are given with three integer values L, R and X. You are asked to add the value X in each of the indices from L to R. Find the maximum value in the array. The Original problem Statement of Array Manipulation is available at Hackerrank.

### Brute Force Solution – O(Q * MAX(R))

For each of the query you’ll simply add the value X from index L to index R and keep doing it for each query. And then find the index where maximum value resides and it’s respective value. For example:

Queries:

L R X : 3 8 5

L R X : 5 7 3

Array (Initially) –

Running the queries normally:

Array after 1st query (3 8 5) –

Array after 2nd query (5 7 3) –

After running all the queries the maximum element from the array can be found in linear time. The answer is 8.

#### Time complexity of Brute Force Solution

Brute Force solution takes O(Q * MAX(R)) time, where Q is the number of queries and MAX(R) is the maximum value of the right index across all queries. This time can be improved using the concept of Difference array as described below.

### Array Manipulation Solution using Difference Array – O(Q + MAX(R))

Many of the times you’ll need to do range-query in an array as is the situation in this problem also. That is where difference array comes into picture. Not only did it optimizes the solution but also makes the question easy to implement. It is used where our solution depends on the final array after doing the range-query on the array and it doesn’t have to do anything when we are actually performing query on the array.

The challenge Array Manipulation seems very easy in the first instance and a straight forward solution is also given above which runs in O(Q * MAX(R)) time. But, look at the constraints, L and R can vary from 1 to 10^{7} and X from 1 to 10^{9}. This big range is going to make the brute force solution very slow. Optimized solution uses the idea of difference array.

Let’s take a query and see it closely to understand what is going on.

1) Adding the value X across all indices from L to R. **[Brute Force Idea]**

2) Adding the value X at index L and subtracting the value X at index (R+1) and taking a prefix sum. **[Difference Array Idea]**

If you look closely the points 1 and 2 are equivalent to each other.

#### Example

Let’s see with a running example.

Queries:

L R X : 3 8 5

L R X : 5 7 3

1) Adding the value X across all indices from L to R. **[Brute Force Idea]**

Array (Initially) –

Running the queries normally:

Array after 1st query (3 8 5) –

Array after 2nd query (5 7 3) –

2) Adding the value X at index L and subtracting the value X at index (R+1) and taking a prefix sum. **[Difference Array Idea]**

**Step 1** – Add the value X at index L and subtract it at index (R+1)

Array (Initially) –

After 1st query (3 8 5) –

Array after 2nd query (5 7 3) –

**Step 2** – Take the prefix sum

The array after doing range-query is same in both the cases. The reason why difference array idea works is because after adding value X at index L, it moves forward when you take the prefix sum. Subtracting it at (R+1)th index basically nullifies its effect beyond index R. So the value X is added to each element only in the range from L to R and this is same as adding the value X from L to R in brute force solution.

#### Time Complexity of Optimized solution

For each query, X is added at index L and subtracted the at index (R+1). This operation is done in O(1) time. So for all Q queries, it takes O(Q) time. After performing all queries, prefix sum is calculated at the end, only once. It takes O(MAX(R)) time. So total time will be O(Q + MAX(R)) which is significantly better than O(Q * MAX(R)).

### C++ Program for Array Manipulation Challenge – Hackerrank

```
#include<bits/stdc++.h>
using namespace std;
int DiffArray[100];
int main(){
int q,l,r,x,m = 0, idx = 0;
// number of queries
cin>>q;
for(int i = 0; i < q; ++i){
// l = left index
// r = right index
// x = value to be added
cin>>l>>r>>x;
// adding the value at lth index
DiffArray[l] += x;
// subtracting the value at (r+1)th index
DiffArray[r + 1] -= x;
m = max(m ,r);
}
// taking the prefix sum
for(int i = 1; i <= m; ++i){
DiffArray[i] += DiffArray[i-1];
if(DiffArray[idx] < DiffArray[i]){
idx = i;
}
}
cout<<idx<<" "<<DiffArray[idx];
}
```

Written By: Shrey Chaurasia

Read Also –

GAME OF TWO STACKS SOLUTION

CONSECUTIVE SUBSEQUENCES SOLUTION

APPEND AND DELETE

ORGANIZING CONTAINERS OF BALLS

INSERTION SORT ADVANCED ANALYSIS

CIRCULAR ARRAY ROTATION

Go To – Hackathon Solutions | Competitive Coding | GATE MCQs

Akhand Pratap SinghGreatðŸ‘Œ