ChandraBhan's blog

Find subarray from given array satisfying a particular condition.
By ChandraBhan, 9 years ago, In English

Given an array and an integer T. We need to find a subarray from I, I + 1, I + 2……..j such that ||a [I] + a [I + 1] + ……. a [j] | – T| is minimum.? Element's can be negative .size of array<=1000000

Link to above problem

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

»
9 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

a[l] + ... + a[j] is equal to S[j + 1] - S[l] where S is the partial sum array S[i] = a[0] + ... + a[i - 1].

So calculate partial sum array, then sort it and use two pointer method to find two indices a, b such that S[b] - S[a] is as close to T as possible.

Calculating partial sum array is O(n), sorting is and two pointers is O(n), so the algorithm is .

EDIT: actual source

→ Reply