### ss_96's blog

By ss_96, history, 2 years ago, , The problem statement:

There is an array given of 1s and -1s and there is a distance K,the output required is the maximum no of pairs such that their sum is 0 and both the numbers are within K distance.

eg: for array:

1 -1 1 -1 and K = 1 answer:2

This can be done with brute force,but i think there would a more efficient algorithm than just brute force.Can anyone please suggest something better,a pseudo code or is there any known algorithm for this?

Edit:A number can be taken only once.

Thanks. c++, Comments (10)
 » In your example, shouldn't the answer be 3? With pair of indexes being: 0,1 & 1,2 & 2,3 .
•  » » A number can be taken only once
•  » » » Well, that simplifies it. You can use two pointers i and j for 1 and -1 respectively. Should be done in O(n) time.
•  » » » » Can you please elaborate a bit about the approach?Thanks
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   I haven't worked it out thoroughly, but you can think on this lines. Index i is used for 1 and index j for -1. Initialize both i=0 and j=0. Increment and i and j till a[i]=1 and a[j]=-1. When a[i] is equal to 1 and a[j] is equal to -1, check the distance. If the distance is greater than k, increase the lesser of i and j, until it is less than or equal to k and sum is 0.
•  » » » » » » Can we use iterative DFS or BFS here.Will it be feasible?
•  » » » » » » » No. I don't think there is a need to do so.
•  » » » » » » » » Alright,Thanks.
 » Auto comment: topic has been updated by ss_96 (previous revision, new revision, compare).
 » for i