Worm walking on a line

By | November 28, 2015
Share the joy

Given a array consisted of only 0 or 1, and a number N.
We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed.

For example, 100100111000, n=2, the best flip is 100111111000, return 6
10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)

The idea is to set a head and tail in array. 0 between head and tail is N. Each time, move head and tail to next 0 position, and calculate the current distance between head and tail.

Because rotation is considered, we should consider about the boundary condition specially:
when number of zero in array equal N+1, should return arr.length-1.
when number of zero is less than N+1, should return arr.length.

So I added isValid to check number of zero.

A typical process without rotation is showed below:

check my code on github: link