Detect all indices of invalid zeroes in the input string (Modify algorithm that I have)

Question

My requirements are as follows:

Input: one array of integer (value will be only 0/1) and an integer ζ

Process: detect all indices of invalid zeroes

An invalid zero is a zero that belongs to a run of 0s whose length is greater than or equal to ζ

Output: ArrayList holding all indices of invalid zeroes

Example:

input:  Data: 1,0,0,0,1,1,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1        
    ζ : 2

output: 2,3,4,17,18

============================================

I am using the following algorithm and want to know if there is a better way to do it?

Algorithm: validate(A[1…n], ζ)

Counter ⇐ 0
For i ⇐ 1 to n do
    if A[i] == 0 then 
        counter ⇐ counter +1
        if i == n and counter >= ζ then
            for j ⇐ (n-counter)   to n do
                R.add(j)
    else
        if counter >= ζ
            for j ⇐ (i-counter-1)   to (i-1) do
                R.add(j)
        counter ⇐ 0
return R

Thanks

Answer 1

I got this O(n) algorithm, although it seems a little bit long.

Algorithm: validate(A[1…n], ζ)
    j ⇐ 0

    // Store all indices of zeroes in Q
    for i ⇐ 1 to n do
    if A[i] == 0 then
        j ⇐ j + 1
        Q[j] ⇐ i

    Qsize ⇐ j

    // if number of zeroes in input is less than ζ, return empty set
    if Qsize < ζ then
        return R //R is an Empty ArrayList

    //if any zero is invalid, return every index in Q
    if ζ == 1 then
        for i ⇐ 1 to Qsize do
            R.add(Q[i])
        return R

    flag ⇐ false
    // one loop to indentify valid zeroes, change their indices to 0
    // only keep invalid zeroes indices in Q
    for i ⇐ Qsize to ζ do   

        if Q[ i – ζ +1] – (i - ζ +1) == Q[i] – i then
            flag ⇐ true
            i ⇐ i – ζ +1 // for-loop will do one more i ⇐ i -1

        else if flag == true and Q[i] - i <> Q[ i + 1 ] – (i + 1) then
            flag ⇐ false
            i ⇐ i  +1 // for-loop will do one more i ⇐ i -1

        else
            Q[i] ⇐ 0

    // Put invalid zeroes indices into R to return
    for i ⇐ 1 to Qsize do
        if Q[i] <> 0 then
            R.add(Q[i])

    return R