HackerRank - Array Manipulation

Question

This is my implementation for this hacker rank problem. (And a follow-up.)

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 and you have to add value k to all the elements ranging from index to (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

First solution

My first attempt I think is quite readable (ignoring the way input and output is handle in hacker rank)

#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> v(n);
    for(int a0 = 0; a0 < m; a0++){
        int start, end, val;
        cin >> start >> end >> val;
        auto it_start = v.begin()+(start-1);
        auto it_end = v.begin()+(end);
        transform(it_start, it_end , it_start, [k](long long &x){return x+=k;});
    }
    cout << *max_element(v.begin(),v.end());
    return 0;
}

Final solution

But this approach, although readable, is too slow for what it is actually being ask, which is the maximum value that it would be achieved. So I wrote this, which passed the tests, but which is more difficult to understand in my opinion.

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    int n; int m;
    std::cin >> n >> m;
    using val_type = long long;
    std::vector<val_type> v(n);
    while(m--){
        val_type start, end, val;
        std::cin >> start >> end >> val;
        auto it_start = v.begin()+(start-1);
        auto it_end   = v.begin()+ end;
        *it_start     += val;
        *it_end       -= val;
    }
    val_type max{0};
    auto accumulate_max_val = [x=val_type(0),&max](val_type y) mutable{x+=y; if (x>max) max=x;};
    std::for_each(v.begin(),v.end(),accumulate_max_val);
    std::cout << max;
    return 0;
}

What would you do to improve it? Am I using lambdas and the for_each appropriately, or is there a clearer way to express what I want to do?

Answer 1

• Kudos for figuring out the correct algorithm.

  However you can streamline it by not using a v vector:

  You correctly treated an operation a, b, k as a pair of operations: add k from a to the end, and subtract k from b+1 to the end. Now, instead of storing them in v, collect decoupled operations in a vector of their own. Sort it by index. std::partial_sum it, and find the maximum in the resulting array.

  This will drive the space complexity down from \$O(n)\$ to \$O(m)\$, and change the time complexity from \$O(n+m)\$ to \$O(m\log m)\$. According to constraints, the time complexity seems to be better. One should also keep in mind that accesses to v could be all over the place with no particular order, and a well crafted sequence of operations may incur too many cache misses. I didn't profile though.

• It is possible that spelling the loop out (rather than using for_each and lambda) would improve readability.

• The algorithm would fail if k was allowed to be negative. Even it is not the case, it still is a good habit to initialize max and x to v[0], and start the loop at v.begin() + 1.