trjhtr

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 max0;
 auto accumulate_max_val = [x=val_type(0),&max](val_type y) mutablex+=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(mlog 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.

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.

See: The Apple documentation for subscript()

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[0] - 1
 let right = query[1] - 1
 let amount = query[2]
 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