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.
makes it O(N+1) instead of O(1) auxiliary space.
plus there is a nasty bug in your code.
you allocate on the heap and you never deallocate it
delete a;
So here is a BETTER solution O(log(N)) time complexity, and O(K) space complexity.
long arrayManipulation(int n, vector<vector<int>> queries)
`{
long max = LONG_MIN;
map<int, long> range;
for(auto el: queries)
{
int a = el[0];
int b = el[1]+1;
int k = el[2];
auto p1 = range.insert(make_pair(a,k));
if(p1.second == false)
p1.first->second += k;
auto p2 = range.insert(make_pair(b, -k));
if( p2.second == false)
p2.first->second -= k;
}
long sum = 0;
for(auto v:range)
{
sum += v.second;
if(max<sum)
max = sum;
}
return max;
}`
In this Approach, you olnly store the boundaries of each range, no need to fill the inbetween zeros,
also searching, inserting and deleting and element in map is O(log(size(map)), which makes the worst case scenario O(log(N)).
any comment or suggestion is welcome.
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 →
creating the array on the heap
long int* a = new long int[N+1]();
makes it O(N+1) instead of O(1) auxiliary space. plus there is a nasty bug in your code. you allocate on the heap and you never deallocate it
delete a;
So here is a BETTER solution O(log(N)) time complexity, and O(K) space complexity.
long arrayManipulation(int n, vector<vector<int>> queries)
`{}`
In this Approach, you olnly store the boundaries of each range, no need to fill the inbetween zeros, also searching, inserting and deleting and element in
map
isO(log(size(map))
, which makes the worst case scenarioO(log(N))
.any comment or suggestion is welcome.