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. – Blasco Jan 18 '18 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 '18 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 – Blasco Jan 18 '18 at 8:26

What I recommend to improve to author - is to move calculation out of IO routines and make reusable function similar to listed below. Below is a Swift version which looks a bit different due Swift syntax. But C/C++ code can be nearly the same with the difference of array allocation.

Swift 4 version.

According to documentation for Array data type the complexity is O(1).

Reading an element from an array is $O(1)$. Writing is $O(1)$ unless the array’s storage is shared with another array, in which case writing is O(n), where n is the length of the array.

So, first we can safely allocate array of needed size. Then we can store intermediate sums at provided boundaries. In second part of calculation we finding maximum by summing intermediate values.

func arrayManipulation(n: Int, queries: [[Int]]) -> Int {

var result = Array(repeating: 0, count: n)

for query in queries {
let left = query - 1
let right = query - 1
let amount = query
result[left] += amount
if (right + 1) < n {
result[right + 1] -= amount
}
}

var max = 0
var x = 0
for i in 0 ..< n {
x += result[i]
if max < x {
max = x
}
}

return max
}
• Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. – Toby Speight Aug 13 '18 at 15:50