Sums for list of ranges (CodeFights Basic Skills)

Question

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
}

Answer 1

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
  

• Yarn: The incrementing/decrementing multiplier is awesome. Thank you.