sagnihotri's blog

Interview Problem
By sagnihotri, history, 7 years ago, In English

Given an array of integers (positive and negative). find the sub-array with sum closest to a number T.
I was asked to answer M queries and in each query we are give number T.
I came up with a solution of nlogn + m*n*logn but interviewer was not satisfied and wanted me to come up with nlogn + m*n solution.

Can anyone suggest me what can be optimised solution for this.
My solution involves storing prefix sum in set and finding prefix[i]-T value in set.

  • Vote: I like it
  • +23
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

An O(N) query is possible using a two-pointer approach.

My Own Question: How would we solve this if numbers could be negative?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it +24 Vote: I do not like it

    That's where the NlogN comes from. You can compute the prefix sums. Then you need to choose to values i and j so that prefix[j] — prefix[i] is close to T and j > i. You can sort the prefix sum array and then do something close to the 2-pointer technique. It seems you might also need to store a deque with the initial positions of those prefixs to look for the closest one that is smaller/larger. Anyway, sorting the prefix sums array enables you to solve it in O(N) per query, just that depending on how you handle the cases, it might become a little dirty

    PS: The main difficulty is that the numbers can be negative. I think you should specify that in the blog. I don't understand why it got so downvoted, the deque solution, at the very least, is kind of cute (or in worst case something neutral, but it's not exactly worth a negative vote)

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

EDIT: sorry I answered something else, please delete

→ Reply