You are viewing a single comment's thread. Return to all comments →
Single Pass O(N) Functional Sol'n
def arrayManipulation(n: Int, queries: Array[Array[Int]]): Long = queries.foldLeft(new Array[Long](n+1)) { case (darr,q) => q match { case Array(start, end, value) => darr(start - 1) += value darr(end) -= value darr }}.scanLeft(0L)(_+_).max
Understand the Difference Array Trick - super simple and effective!
Make arr size n+1 so we can add to end if its the Last item (or ignore)
only Mark the Starts with +query and mark the end+1 index with a -ve value [100, 500 , 0 , 200 , -100 , -500 , 0 , -200 ]
Then simply compute the Prefix Array in a Single Pass
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 →
Single Pass O(N) Functional Sol'n
Understand the Difference Array Trick - super simple and effective!
Make arr size n+1 so we can add to end if its the Last item (or ignore)
only Mark the Starts with +query and mark the end+1 index with a -ve value [100, 500 , 0 , 200 , -100 , -500 , 0 , -200 ]
Then simply compute the Prefix Array in a Single Pass