Range Update’s In A Array

Shankar Shastri
Sep 9, 2018 · 3 min read

Problem URL: https://www.hackerrank.com/challenges/crush/problem

A very nice problem to be solved on Hackerrank. I will explain the way I went ahead in solving the problem in Scala with different approaches in a functional manner. The problem mainly deals with range-updates of the array(Zero-Filled-N-Size-1-Indexed-Array), given (startingIndex, endingIndex, valueToBeAdded), N(Size Of Array) and Q(No: Of Queries). And the array indexes given are 1-indexed. We need to figure out the max value in the array after range-updates.

Test-Case Constraints:

(ImgSrc: https://www.hackerrank.com/challenges/crush/problem)

Example:

Input:
5 3
1 2 100
2 5 100
3 4 100
Output:
200
Steps:
(BruteForce Solution For Easy Understanding)
Given:
N = 5, Q = 3, Arr=[0, 0, 0, 0, 0]Note: The Array Indexed Are 1-indexed.1st Query: Arr = [0, 0, 0, 0, 0] => [100, 100, 0, 0, 0]
(Add 100 to array index starting from 1 to 2)
2nd Query: Arr = [100, 100, 0, 0, 0] => [100, 200, 100, 100, 100]
(Add 100 to array index starting from 2 to 5)
3rd Query: Arr = [100, 200, 100, 100, 100] => [100, 200, 200, 200, 100]
(Add 100 to array index starting from 3 to 4)
Resultant Array After Range Updates:
Arr = [100, 200, 200, 200, 100]
MaxInArr = 200 // Answer

Brute-Force Approach:

The above solution demonstrates the brute-force approach of solving the problem. It’s straightforward from code

{
queries.foreach {
e => {
val Array(a, b, k) = e
(a to b).foreach(ele => arr.update(ele, arr(ele) + k))
println(arr.mkString(" "))
}
}
arr.max.longValue()
}
The first foreach is getting each query from query array, and the second foreach updates the respective array index by adding K value.

The complexity of this solution is O(m*n). But with the test-case constraint, the brute-force solution doesn’t pass.

Optimal Approach:

Before we dig into the optimal solution let’s understand the prefix-sum problem.

From Wikipedia, the free encyclopedia

In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, … is a second sequence of numbers y0, y1, y2, …, the sums of prefixes (running totals) of the input sequence.

The above solution solves the problem using the Prefix-Sum approach.

{
queries.foreach { e =>
{
val Array(a, b, k) = e
arr.update(a - 1, arr(a-1) + k)
if (b < n)
arr.update(b, arr(b) - k)
println(arr.mkString(" "))

}
}
arr
.foldLeft(BigInt(0), BigInt(0))((a, b) => {
(a._1 + b, a._2.max(a._1 + b))
})
._2
.longValue
}
The above code snippet is the core-algo of the problem. It solves by adding the k value in arr(a-1) and subtracting k value in arr(b).
This kind of update, updates the array with prefix sum starting from array index 0 to i(being any index). The prefix sum algorithm will give us the fully updated array with all indexes updated with the respective values.The below foldleft helps in computing the max using the prefix sum.

Using this approach, the updates in the array will reach O(m) time. And to calculate all the prefix sums as well as maximum prefix sum it requires O(n). The complexity of this solution is O(m+n).

Full Solution:

References:

Wrapping it Up:

If you have suggestions that I missed above, let me know in the responses!

If you found this helpful, click the 💚 so more people will see it here on Medium.

Shankar Shastri

Written by

Functional Programmer => Scala Enthusiast.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade