# HackerRank - Array Manipulation

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?

• 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, and start the loop at v.begin() + 1.

• Thank you for your feedback. How do you know this is the "correct" algorithm? And how do you compute the time complexity to know that with your proposed method is O(m log m)? I thought your suggestions could be implemented with a map, I don't know if I understood right what you are trying to tell me. Jan 18, 2018 at 7:35
• @WooWapDaBug It is hard to answer how. It feels right (call it experience). It doesn't brute force. It passes the test cases, which makes it right. $O(m\log m)$ comes from the sorting. I don't think map may change the bottomline: if the map gives better performance, it would mean you can sort faster.
– vnp
Jan 18, 2018 at 8:24
• Oh, I didn't mean it would change anything, I just thought it was an easy way to implement the sorting + indexing in just one small change Jan 18, 2018 at 8:26