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) |
where |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(nn 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 didn’t clear the round.
Can anyone give hint for this?
I asked the question on Stackoverflow as well.