You are viewing a single comment's thread. Return to all comments →
I took the ideas explained here to put also into python in a bit more spelled-out way to help make sense of this more abstract work-around.
def arrayManipulation(n, queries):
# Big O (N)
res = *(n+1) # we only really need one terminal row, since we're applying each pass to all rows below
# loop through all the queries and apply the increments/decrements for each
# Big O (M) (size of queires)
for row in range(len(queries)):
a = queries[row]
b = queries[row]
k = queries[row]
res[a-1] += k # increment the starting position
# this is where a loop would increment everything else between a & b by k
# but instead of taking b-a steps, we take a constant 2 steps, saving huge on time
res[b] -= k # decrement the position AFTER the ending position
# now loop through res one time - Big O (N) (size of res)
sm = 0 # running sum
mx = 0 # maximum value found so far
for i in range(len(res)):
sm += res[i]
if sm > mx:
mx = sm
# total run time is Big O (2*N + M) >> Big O(N)
The key concepts in my opinion here are:
1) we don't need to build the full aray, since it's impossible for any row but the last to have the max value. This is impossible because we apply the adjustments to every subsequent row of the resulting 2-D array.
2) we don't need to actually increment each value for indices 'a' through 'b'. While that's the most straight-forward way, that also requires x many (a minus b) steps for each pass of the loop. By noting instead where to start incrementing and where to stop incrementing (noted by decrementing after what would be the final increment), we can note the adjustments to apply without having to take every step each time. We can then run a separate single loop to go over each of the increments and keep a running sum of all the overlapping increments. The decrement allows us to know when that range where the increment applied is over by reducing the running sum by that number - in other words when that range is ended, we would have to look at overlapping increments excluding that one that just ended going forward to see if anything is bigger.
Someone else in here gave an image of a stair/hill which I found extremely helpful in visualizing and understanding this concept. The basic idea here is that instead of actually applying each increment, we can just note what the increment and range is and one by one go through each place and apply all the compounded increments at once. Loop 1 saves the increments in a different format, Loop 2 checks the overlap. And by using two separate loops we have basically Big O (N) rather than Big O (N^2) - or more specifically Big O (2N + M) instead of Big O (NM + N), where N is the size of the resulting array and M is the size of the queries array.