Блог пользователя sagnihotri

Interview Problem
Автор sagnihotri, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +24 Проголосовать: не нравится

    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)

    → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

EDIT: sorry I answered something else, please delete

→ Ответить