Question:
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.
For example, the length of your array of zeros . Your list of queries is as follows:
a b k
1 5 3
4 8 7
6 9 1
Add the values of between the indices and 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 largest value is after all operations are performed.
Function Description
Complete the function arrayManipulation in the editor below. It must return an integer, the maximum value in the resulting array.
arrayManipulation has the following parameters:
- n - the number of elements in your array
- queries - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.
Input Format
The first line contains two space-separated integers and , the size of the array and the number of operations.
Each of the next lines contains three space-separated integers , and , the left index, right index and sum.
Each of the next lines contains three space-separated integers , and , the left index, right index and sum.
Output Format
Return the integer maximum value in the finished array.
Sample Input
5 3
1 2 100
2 5 100
3 4 100
Sample Output
200
Explanation
After the first update list will be
After the second update list will be
After the third update list will be
The required answer will be . 200
100 100 0 0 0
.After the second update list will be
100 200 100 100 100
.After the third update list will be
100 200 200 200 100
.The required answer will be . 200
Solution:
Brute Force:
The first solution is pretty intuitive and follows a brute force approach.
Steps for brute force approach:
- Create a long array of size 10^7.
- For each range update add the K to all values in that range from a to b.
- Scan through the entire array and find the maximum value found.
The solution is very easy so I am not attaching the code here as it will result in timeout.
The time complexity of this solution would be O(m*n)
Optimal Solution:
The optimal solution forces us to think on optimising the usage of ranges.
Steps:
- First we create a new class Range with two fields start(a or b) and the value (k).
- We will create an ArrayList ( we code in Java right) of the new class object which is declared as Range in the code.
- Now for each of the m queries we will create two Range objects and insert them in the list.
- TRICK: now for every start in the query we will add the weight K to the range and for every b in the the query we will create a new Range object with b+1 with weight -k.
- Let the above line register in your mind and think over it, now we will simply sort the custom list on the basis of start value and we will have to be cautious while defining the comparator because some test case will fail if you don't take are of edge cases.
- We have the sorted ranges now in the list we just have create a sum variable and max variable sum wil keep on adding weights from the list and max will keep track of the max sum encountered so far.
- Return the max.
- The EDGE CASE: when we have a tie on the start value then we have to give preference to the negative value.
Example of edge case:
4 3
2 3 603
1 1 286
4 4 882
The Correct answer will be 882 and not 889 just think over it you will understand it, I know you will.
The Code is shared below.
static class Range{
long start;
long value;
Range(long start, long val){
this.start = start;
this.value = val;
}
}
static long arrayManipulation(int n, int[][] queries) {
List<Range> ranges = new ArrayList();
long sum=0 , max=0;
for(int i = 0; i < queries.length; i++){
ranges.add(new Range(queries[i][0], queries[i][2]));// adding k at start
ranges.add(new Range(queries[i][1] + 1, queries[i][2]*-1));//subtracting k at end + 1
}
Collections.sort(ranges, (n1, n2) ->{
if(n1.start - n2.start == 0){
if(n1.value < 0) return -1;
return 1;
}
else return (int) (n1.start-n2.start);});
for(Range r: ranges){
sum += r.value;
max = Math.max(sum , max);
}
return max;
}
The time complexity of the above code if you have not guessed till now is O(mlogm).
Why O(mlogm) ?
Because first we have accessed m queries -> O(m).
we created 2m objects from the queries and then sorted the list. -> O(2m log2m) -> O(mlogm).
Then we iterated over the list. -> O(2m) -> O(m).
the max of all three was O(mlogm).
I have seen it was given wrong at a lot of places and blogs.
Thanks for reading.
Array Manipulation Hackerrank Solution in Java
Reviewed by Jas Arora
on
June 03, 2020
Rating:
No comments:
If you have any doubts please let me know.