We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Used the idea o modifiers, but without the n-sized array. Also in C#. Complexity is O(m log m), that can be less than O(n).
static long arrayManipulation(int n, int m, int[][] queries) {
long max = 0;
SortedDictionary<int,long> fakeArray = new SortedDictionary<int,long>();
// 'm' times
for (int i=0; i<m; i++) {
int a = queries[i][0];
int b = queries[i][1];
int k = queries[i][2];
// bit optimization: a '0' valued query will make no difference on resultant ones
if (queries[i][2] <= 0) continue;
if (!fakeArray.ContainsKey(a)) { // O( log m )
fakeArray.Add(a, k); // O( log m )
}
else {
fakeArray[a] += k; // O( log m )
}
if (b < n) {
b++;
if (!fakeArray.ContainsKey(b)) { // O( log m )
fakeArray.Add(b, -1 * k); // O( log m )
}
else {
fakeArray[b] -= k; // O( log m )
}
}
}
long current = 0;
foreach(long modifier in fakeArray.Values){ // O( 2*m )
current += modifier;
if (current > max) max = current;
}
return max;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
Used the idea o modifiers, but without the n-sized array. Also in C#. Complexity is O(m log m), that can be less than O(n).