Sums for list of ranges (CodeFights Basic Skills)

I can solve this problem with a brute force naive solution, but need to optimize it for time. I'm not in school, but trying to learn fundamentals on my own.

I know I need to store the sum of the indices already counted so that I am not recounting ranges I've already covered. Like in the example below if I already summed [0,2] and [2, 5] I could just add those sums to get [0, 5] sum without iterating over array. But I don't know how to implement this.

Here is the description:

You have an array of integers nums and an array queries, where queries[i] is a pair of indices (0-based). Find the sum of the elements in nums from the indices at queries[i][0] to queries[i][1] (inclusive) for each query, then add all of the sums for all the queries together. Return that number modulo 10^9 + 7.

Example:

For nums = [3, 0, -2, 6, -3, 2] and queries = [[0, 2], [2, 5], [0, 5]], the output should be sumInRange(nums, queries) = 10.

The array of results for queries is [1, 3, 6], so the answer is 1 + 3 + 6 = 10.

My solution:

func sumInRange(nums: [Int], queries: [[Int]]) -> Int {

var sumArray = [Int]()

for q in queries {

var tempSum = 0

for i in q[0]...q[1] {

tempSum += nums[i]
}

sumArray += [tempSum]
}

let sum = sumArray.reduce(0, +)
let bigNumber = 1000000000 + 7

return sum > 0 ? sum % bigNumber : bigNumber + sum
}


First let's simplify your existing code.

You already use reduce() to add the elements of sumArray, the same can be done to replace

    var tempSum = 0
for i in q[0]...q[1] {
tempSum += nums[i]
}


by

let tempSum = nums[q[0]...q[1]].reduce(0, +)


Here an "array slice" is created and then reduced. Note that this does not duplicate the element storage.

Instead of appending a single-element array

   sumArray += [tempSum]


you can append a single element:

sumArray.append(tempSum)


Each element sumArray is the result of applying one query to the given numbers, this can be simpler done as a map operation:

let sumArray = queries.map { q in
nums[q[0]...q[1]].reduce(0, +)
}


I would define the modulus $10^9+7$ as a constant (interspersed with _ for better readability):

let modulus = 1_000_000_000 + 7


There is one problem at your

return sum > 0 ? sum % bigNumber : bigNumber + sum


which becomes apparent only with large input: A negative sum must also be reduced modulo $10^9+7$, before adding the modulus to make it non-negative.

Putting it together, your code would look like this:

func sumInRange(nums: [Int], queries: [[Int]]) -> Int {

let sumArray = queries.map { q in
nums[q[0]...q[1]].reduce(0, +)
}

let sum = sumArray.reduce(0, +)

let result = sum % modulus
return result >= 0 ? result : result + modulus
}


which is probably not faster, but simpler and cleaner ("Swiftier") code.

In order to pass the coding challenge in the given time, you need a different algorithm. The idea is (and to be honest, I did not invent this myself but found it here):

• First create hashes (dictionaries) which associate with every index the number of queries starting (resp. ending) at this index.
• Then traverse the nums array once, keeping track of a "multiplier" which indicates how often the number at the current index occurs in the queries, and accumulate the sum.

An implementation in Swift could look like this:

func sumInRange(nums: [Int], queries: [[Int]]) -> Int {
var startIndices: [Int: Int] = [:]
var endIndices: [Int: Int] = [:]

for q in queries {
startIndices[q[0], default: 0] += 1
endIndices[q[1], default: 0] += 1
}

var multiplier = 0
var sum = 0
for (idx, num) in nums.enumerated() {
multiplier += startIndices[idx] ?? 0
sum += num * multiplier
multiplier -= endIndices[idx] ?? 0
}

let result = sum % modulus
return result >= 0 ? result : result + modulus
}


Further remarks:

• You probably need to reduce modulo $10^9+7$ not only the final sum but also the intermediate results, in order to avoid an integer overflow.

• A Swiftier way to represent pairs is to use tuples instead of two-element arrays:

func sumInRange(nums: [Int], queries: [(from: Int, to: Int)]) -> Int

• The incrementing/decrementing multiplier is awesome. Thank you. – Yarn Jan 23 '18 at 23:41