Given an array A and m queries each query is integer T
For each query find index i and j such that
| (|sum of elements from i to j| - T) |
is minimum
wher |x| is abs(x) and array can have negative numbers as well
I was asked this question in directi interview. I had the solution of finding all possible sum and store their indices and sort.
so there will be n*n sums possible.
That would take O(n* n* log(n*n))
now for each query binary search T .That would be O(m* log(n*n))
But he asked to optimize it.I didnt clear the round.
Can anyone give hint for this?
If we sort the partial sums, for example,
A = [2, -4, 6, -3, 9]
ps = [2, -2, 4, 1, 10]
sorted = [-2, 1, 2, 4, 10]
the minimum absolute value of the sum represents the smallest difference between partial sums; in this case, 1 and 2, representing a sum of:
-4 + 6 - 3 = -1
Since we'd like to minimise yet another absolute value of a sum, we want to find the absolute sum difference that's closest to T. I could not find a reference for finding a pair with closest difference to a constant in less than O(n) time, so as is, this approach does not seem better than O(n * log n + n * m). Perhaps we can take advantage of hashing or sorting the queries first since queries that are close to each other represent close ranges during our search, but I'm not sure how.