Array Manipulation Solution

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) –

Array Manipulation Solution

Running the queries normally:

Array after 1st query (3 8 5) –

Array Manipulation Solution

Array after 2nd query (5 7 3) –

Array Manipulation Solution

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 107 and X from 1 to 109. 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) –

Array Manipulation Solution

Running the queries normally:

Array after 1st query (3 8 5) –

Array Manipulation Solution

Array after 2nd query (5 7 3) –

Array Manipulation Solution

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) –

Array Manipulation Solution

After 1st query (3 8 5) –

Array Manipulation Solution

Array after 2nd query (5 7 3) –

Array Manipulation Solution

Step 2 – Take the prefix sum

Array Manipulation Solution

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

Spread the love

1 thought on “Array Manipulation Solution”

Leave a Comment

Your email address will not be published. Required fields are marked *