CODEWITHSUNDEEP
algorithmintervalspascallazarus
PortalArmy
PortalArmy

Reputation: 21

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.

Upvotes: 1

Views: 98

Answers (2)

Erfan Alimohammadi
Erfan Alimohammadi

Reputation: 480

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

Upvotes: 1

Prune
Prune

Reputation: 77837

First, for clarity in the algorithm, I'm going to change the numbers to letters: Z, A, B. The input can now be represented as a simple string: "ZAABB". Also for clarity, I'm going to insert a period at each position, for spacing: ".Z.A.A.B.B.".

This is a symbol balancing problem, easy enough to handle. Iterate through the array, keeping track of the excess at each position. Z doesn't change the count; A increments; B decrements. This gives us 

"00011221100".

Now, extract alternate counts, the count at each "spacer", the periods: 

".Z.A.A.B.B."
"0 0 1 2 1 0"

From here, its simple to find matching counts. Every pair of matching counts gives you the indices of a substring with the same quantity of A and B. You have three pairs of 0 matches and one pair of 1 matches, yielding the substrings

"0 0 1 2 1 0" Z

"0 0 1 2 1 0" Z A A B B

"0 0 1 2 1 0" A A B B

"0 0 1 2 1 0" A B

Is that clear enough for you to implement?

Upvotes: 2

Related Questions