# Array Manipulation | HackerRank Solution [Hard]

Problem

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

###### Input

The first line contains two space-separated integers n and m, the size of the array and the number of operations.
Each of the next m lines contains three space-separated integers ab and k, the left index, right index and summand.

###### Output

int: the maximum value in the resultant array

###### Constraints
• 1 <= n <= 107
• 1 <= m <= 2 x 105
• 1 <= a <= b <= n
• 1 <= k <= 107
###### Sample Input
5 3
1 2 100
2 5 100
3 4 100
###### Sample Output
200

Explanation
After the first update the list is 100 100 0 0 0.
After the second update list is 100 200 100 100 100.
After the third update list is 100 200 200 200 100.

The maximum value is 200.
###### Solution

Approach: Optimal Brute Force and Sorting

Code Implementation

//
//  main.cpp
//  Array Manipulation
//
//  Created by Himanshu on 30/03/22.
//

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;

//Custom comparator to sort operations (a, b, k)
//in ascending order based on 'a'
bool cmp (const tuple<ll, ll, ll> &e, const tuple<ll, ll, ll> &f) {
if (get<0>(e) == get<0>(f)) {
return (get<1>(e) <= get<1>(f));
} else {
return (get<0>(e) <= get<0>(f));
}
}

//Custom comparator to sort operations (a, b, k)
//in ascending order based on 'b'
bool cmp2 (const tuple<ll, ll, ll> &e, const tuple<ll, ll, ll> &f) {
if (get<1>(e) == get<1>(f)) {
return (get<0>(e) <= get<0>(f));
} else {
return (get<1>(e) <= get<1>(f));
}
}

int main() {
ll n, m, a, b, k;
ll inc = 0, leftIdx = 0, rightIdx = 0, ans = INT_MIN;

cin>>n>>m;
vector<tuple<ll, ll, ll>> inp1, inp2;

for (int i=0; i<m; i++) {
cin>>a>>b>>k;

inp1.push_back(make_tuple(a, b, k));
inp2.push_back(make_tuple(a, b, k));
}

sort(inp1.begin(), inp1.end(), &cmp);
sort(inp2.begin(), inp2.end(), &cmp2);

for (int i=0; i<=n; i++) {

//Add the value 'k' to the ans,
//if i is in range, or equal to 'a'
while (i == get<0>(inp1[leftIdx])) {
inc += get<2>(inp1[leftIdx]);
leftIdx++;
}

//Subtract the value 'k' from the ans,
//if i is not in range, or greater than 'b'
while (i == get<1>(inp2[rightIdx]) + 1) {
inc -= get<2>(inp2[rightIdx]);
rightIdx++;
}

//Select the max values as ans
ans = max(ans, inc);
}

cout<<ans;
return 0;
}


Time complexity: O(n + mlogm)