HackerRank - Array Manipulation - Follow-up

Question

This is a follow-up question for HackerRank - Array Manipulation

Problem

You are given a list (1-indexed) of size \$n\$, initialized with zeroes. You have to perform \$m\$ operations on the list and output the maximum of final values of all the elements in the list. For every operation, you are given three integers \$a\$, \$b\$ and \$k\$ and you have to add value \$k\$ to all the elements ranging from index \$a\$ to \$b\$ (both inclusive).

Example input

5 3
1 2 100
2 5 100
3 4 100

Expected output

200

Explanation

After first update list will be:

100 100 0 0 0

After second update list will be:

100 200 100 100 100

After third update list will be:

100 200 200 200 100

So the required answer will be: 200

Final solution

I changed the way of storing the values, which now get indexed into a map. I think now it's efficient in time and space, my main questions left are about style (taking into account the impositions of the hacker rank input output).

#include <algorithm>
#include <iostream>
#include <map>

int main() {
    int n; int m;
    std::cin >> n >> m;
    using val_type = long long;
    std::map<int,val_type> map;
    while(m--){
        val_type start, end, val;
        std::cin >> start >> end >> val;
        map[start] += val;
        map[end+1] -= val;
    }
    val_type max{0};
    val_type partial_sum{0};
    for (const auto& el : map) {
        partial_sum += el.second;
        if (partial_sum > max) {
            max = partial_sum;
        }
    }
    std::cout << max;
    return 0;
}

I don't like for example that I need to declare the variable partial_sum outside the for loop, being in the same scope as max. Any idea on how to write this partial sum to find the max cleaner?

Answer 1

Whitespace, let your code breathe

Your code has a few logical sections, you should use empty lines to break them appart visually. It makes your code easier to read.

Personal opinion: front-load your type aliases

General wisdom in C++ is to define things as close as possible to their first use, but that's generally meant for objects with lifetimes. I personally prefer to put any type alias at the start of its scope.

algorithm is unused, so it should not be included

Simple enough: do not #include stuff you don't need.

That's kind of it, really, good job!

Edit: to answer your question, you could finagle something with std::accumulate, or just create a scope for partial_sum, but it's not worth the trouble. What you have it fine.

Answer 2

1. Start with a comment telling what problem your code solves, possibly the algorithm you used, and a link to relevant references. You might want to quote part of them too!

2. You don't use anything from <algorithm>, so you should not include it. Well, if you follow the other tips, you will end up using it, but need <vector> and <utility> instead of <map>.

3. If you use constants, typedefs, preprocessor-symbols or the like to ease some customization or tuning, put them as early as possible, but after the includes.

4. Use the nomenclature of the reference, the subject-area if no reference, use descriptive names, or at least idiomatic ones.
   But refrain from inventing your own ad-hoc shorthand, that's cryptic instead of poignant.

5. There's nothing wrong with defining multiple variables at once, in principle.
   But they should be a single declaration, not multiple ones separated by semicolon.

6. Consider inserting a newline between sections to help readers easily find them.

7. Remember that input is often wrong. So check, or for such a short script, maybe enable exceptions on error.

8. Using a std::map works. But it's strictly speaking the wrong data-structure considering the access-pattern. Use a std::vector<std::pair<int, val_type>>, possibly with a call to .reserve(2 * m) to avoid re-allocation, and then do a std::sort().

9. Even the last line of output should be terminated with a new-line. Shells expect that, as do many other programs, and most users.

10. return 0; is implicit in main(), so no need to write it.

Answer 3

Constraints-

3≤𝑁≤10^7

1≤𝑀≤2⋅10^5

1≤𝑎≤𝑏≤𝑁

0≤𝑘≤10^9

Why your brute force solution will not work?

Today generation system can perform 10^8 operation in one second. keep this in mind you have to process N=10^7 input per query in worse case. so if you use your solution with O(NM) complexity it has to handle (10^7 *10 ^5)= 10^12 operation in worse case (which can not be computed in 1 sec at all)

That is the reason you will get the time out error for your brute force solution. So you need to optimise your code which can be done with the help of prefix sum array.

instead of adding k to all the elements within a range from a to b in an array, accumulate the difference array

Whenever we add anything at any index into an array and apply prefix sum algorithm the same element will be added to every element till the end of the array.

ex- n=5, m=1, a=2 b=5 k=5

    i     0.....1.....2.....3.....4.....5.....6   //take array of size N+2 to avoid index out of bound
  A[i]    0     0     0     0     0     0     0

Add k=5 to at a=2

A[a]=A[a]+k // start index from where k element should be added

     i    0.....1.....2.....3.....4.....5.....6 
   A[i]   0     0     5     0     0     0     0

now apply prefix sum algorithm

     i    0.....1.....2.....3.....4.....5.....6 
  A[i]    0     0     5     5     5     5     5

so you can see K=5 add to all the element till the end after applying prefix sum but we don't have to add k till the end. so to negate this effect we have to add -K also after b+1 index so that only from [a,b] range only will have K element addition effect.

A[b+1]=A[b]-k // to remove the effect of previously added k element after bth index. that's why adding -k in the initial array along with +k.

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     0     0     0    -5

Now apply prefix sum Array

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     5     5     5     0

You can see now K=5 got added from a=2 to b=5 which was expected. Here we are only updating two indices for every query so complexity will be O(1).

Now apply the same algorithm in the input

         # 0.....1.....2.....3.....4.....5.....6    //taken array of size N+2 to avoid index out of bound
5 3      # 0     0     0     0     0     0     0
1 2 100  # 0    100    0   -100    0     0     0       
2 5 100  # 0    100   100  -100    0     0   -100
3 4 100  # 0    100   100    0     0  -100   -100

To calculate the max prefix sum, accumulate the difference array to 𝑁 while taking the maximum accumulated prefix.

After performing all the operation now apply prefix sum Array

    i      0.....1.....2.....3.....4.....5.....6 
  A[i]     0     100   200  200   200   100    0

Now you can traverse this array to find max which is 200. traversing the array will take O(N) time and updating the two indices for each query will take O(1)* number of queries(m)

overall complexity=O(N)+O(M) = O(N+M)

it means = (10^7+10^5) which is less than 10^8 (per second)

Here is the code:

static long arrayManipulation(int n, int[][] queries) {

        long outputArray[] = new long[n + 2];
        for (int i = 0; i < queries.length; i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            int k = queries[i][2];
            outputArray[a] += k;
            outputArray[b+1] -= k;
        }
        long max = getMax(outputArray);
        return max;
    }

    /**
     * @param inputArray
     * @return
     */
    private static long getMax(long[] inputArray) {
        long max = Long.MIN_VALUE;
        long sum = 0;
        for (int i = 0; i < inputArray.length; i++) {
            sum += inputArray[i];
            max = Math.max(max, sum);
        }
        return max;

Note: If searching for video tutorial , you must check it out here for detailed explanation.