2
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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
    
\$\endgroup\$
  • \$\begingroup\$ The incrementing/decrementing multiplier is awesome. Thank you. \$\endgroup\$ – Yarn Jan 23 '18 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.