Search code examples
algorithmintervalspascallazarus

Searching for all intervals meeting a specific condition

How can I search for all intervals in an array of 0s, 1s and 2s that contain the same amount of 1s and 2s?

Example:

[0,1,1,2,2]

Would return 3 intervals

[0,1,1,2,2] [1,1,2,2] [1,2]

I don't want to brute force it. Is there any very simple algorithm which can be used for such instances? I'd need something flexible.

Solution

  • Put -1 instead of 2 in the original array. Then, the problem will be reduced to this: Zero sum SubArray