Array Manipulation Hackerrank Solution in Java

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.

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 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.