Algorithm that finds the start and the finish of many sub-arrays?

Question

so I have this question in C:

Given an array that only contains 0's and 1's (Example: [1,1,0,0,0,0,1,0,1,0,1,1]). I need to find the start of a "ring interval" and the finish of the same "ring interval" (there could be many rings like that, we'll have to store the start and finish of each one in a matrix of 2 columns)

"Silence" is when at least two 0's are next to each other. (in the given array, the sub array [0,0,0,0] is silent.

"Ring interval" is when Silence doesn't occur. (example in the given array, the sub array [1,1] (first 2 values), and the sub array [1,0,1,0,1,1] (the end of the array)).

So we'll have to store [0,1] in the first row of the matrix. then [6,11]. since the second sub array starts at the 6th index and ends at the 11th.

I can't seem to describe it any better, it's in a different language and quite a bit more complicated than this.. i hope you understand!

Examples: Array = [0,0,0,0,1,0,1,1,1,0,0,0,1,0,0] Matrix would be : [4,8] [12,12]

Array = [1,0,0,1,1] Matrix would be : [0,0] [3,4]

Thank you!

Answer 1

I have a simple algorithm for this that you can quite easily translate to C with a bit of research. You could also translate it to basically any other language as well:

Step 1) create two boolean values. One will be true if there is currently a "silence", the other will be true if the last value seen was a zero. Both of these should be true. If we do not assume that there are infinite zeros before the first element of the array, then there will be problems if the first number in the array is zero.

Step 2) loop over the array and check against one of 2 conditions: a) If you see a 1, set silence to false, previousZero to false. If this 1 breaks a silence, store this value as it is the beginning of your next range. b) If the value is zero and there is not a silence, set previousZero to true. If previousZero was already true, you have reached a silence, so set silence to true and store your beginning position and end position in your output array. Your end position in this situation would be the current position -2 to account for the zeros you just examined

Step 3) once you've looped through the entire array, you need to make sure you didn't end on a valid range. if silence is false, you know you ended on a valid range. store this range in your output array by using the begin value you stored in your loop and the end of the array as the end value.

This algorithm runs in linear time. Here is some pseudo-code to get you started on your implementation in C or whatever you choose.

findRing(Array arr)
    bool silence = true, previousZero = true;
    int currentBegin = 0, currentEnd = 0;
    for( int i = 0; i<arr.length; i++) { 
        if(arr[i] == 1)
            if(silence == true)
                currentBegin = i;
            silence = false;
            previousZero = false;
        else if(arr[i] == 0 && silence == false)
            if(previousZero)
                silence = true;
                currentEnd = 1-2;
                addToOutput(currentBegin, currentEnd);
            else
                previousZero = true;
    }
    if(silence == false)
        currentEnd = arr.length - 1;
        addToOutput(currentBegin, currentEnd);

I implemented this pseudo-code in C++ and got the same outputs you provided in your examples. It should be easy to implement in C or Matlab as you mentioned and runs in O(n) time.