### Amit9's blog

By Amit9, 4 weeks ago,

Why this approach fails, can anyone give some counter test case?

• +1

 » 4 weeks ago, # |   0 Consider array 0 1 1 0 1 1 0, target sum is 1. Clearly it can't be done in less than 5 operations, because you must remove at least two 0s to be able to remove at least three 1s. But your approach would remove both outer zeros and set zero to 1, then remove 3 more 1s, leading to a total cost of 4. It doesn't take into account that both outer 0s had to be removed.
•  » » 4 weeks ago, # ^ |   0 Thank you, i haven't noticed it.
 » 4 weeks ago, # | ← Rev. 3 →   0 10 2 0 1 0 0 1 1 0 0 1 0 The correct answer is 4 your algorithm returns 3. The reason it fails in this case is that it performs the correct steps but only counts removing zeros from both ends as 1 operation. (the last else statement in your loop)If you correct it your approach will still be incorrect as in the case: 10 2 0 0 0 1 1 1 1 0 0 0 After the fix your algorithm will return 8, instead of the correct 5 (it remove the first 5 numbers)As far as I know there is no greedy solution to the problem.This problem is equivalent to finding a subarray of maximum size with a sum equal to K (the numbers you leave). This can be solved with a sliding window.
•  » » 4 weeks ago, # ^ |   +3 Thank you.Yeah, i later tried sliding window and it worked, i was just curious whether it can be done with two pointers alone but it doesn't seem to work. thank you once again.