improving time complexity

[Adm666]

is there anyway to improve my code's time complexity or memory's complexity ? (without using advanced methods - im a beginner)
its a method that gets an array filled with zeroes and other numbers, and it changes each number(which is not a zero) to the distance of the closest zero to it.
for example this array: { 1 , 0 , 2 , 5 , 1 , 3 , 0 , 1 , 1 , 0 }
will be changed into this: {1 , 0 , 1 , 2 , 2 , 1 , 0 , 1 , 1 , 0}

for (int i=0; i<a.length; i++)
        {
            if (a[i]!=0){
                int right=0, left=0;
                for (int j=i; j>=0; j--) //count zeroes from the left side
                {
                    if (a[j]!=0)
                        ++left;
                    else
                        break;
                }
                for (int k=i; k<a.length; k++) //count zeroes from right side
                    if (a[k]!=0)
                        ++right;
                    else
                        break;
                a[i]=Math.min(right,left); //finds the closest zero
            }
            else 
                continue;
        }

[Dani]

I'm not a java developer ... However, if I follow your logic correctly, you're checking to the left side. Then, if it's not 0 itself, then you check from the right side. Well, if it's not a 0 itself, then the closest we can be to it is 1. Therefore, if it's already a 1 from the left side, there should be no need to then check the right side because it can't be anything better.

In fact, taking that a step further, you first count from the left, then you count from the right. Then, you figure out which one is lowest. Well, I think instead maybe you should be counting from the left, as you are, and then store that number. Then, count from the right only up to the number we counted from the left. Once we hit it, we know that the left is closest, and we can just break.

This saves us having to continue looping on the right when it's clear the answer is already the left's result. Plus, we can get rid of the expensive Math.min() function.

[AssertNull]

How about creating an array containing the indexes of the zeroes? For your array

{ 1 , 0 , 2 , 5 , 1 , 3 , 0 , 1 , 1 , 0 }

Your zeroes would be at indexes {1, 6, 9}. Creating this array requires one pass through the original array.

int []indexes = new int[a.length];
int numZeroes = 0;
for (int i=0; i<a.length; i++)
{
    if(a[i] == 0)
    {
        indexes[numZeroes] = i;
        numZeroes++;
    }
}

Now imagine your a[] array is a long thin lake and you get numZeroes helicopters, and each helicopter hovers above one of the zero indexes. At the signal, someone in each helicopter drops a big boulder straight down. The analogy gets a tad goofy here, but imagine we're talking about a REALLY big boulder dropped from really high up. At the location of each boulder target, you have two surfers who ride the wave that the boulder creates in either direction. As they pass each index, they take note of the distance they've travelled. They do this until they collide with another surfer or they reach the end of the water/array.

For a short array like your, you'll see little difference, but for a long one, all of those unnecessary loops add up. See code below.

        int []indexes = new int[a.length];
        int numZeroes = 0;
        for (int i=0; i<a.length; i++)
        {
            if(a[i] == 0)
            {
                indexes[numZeroes] = i;
                numZeroes++;
            }
        }
        if(numZeroes > 0)
        {
            int leftZeroIndex, rightZeroIndex;            
            // fill in leftmost elements
            leftZeroIndex = indexes[0];
            for(int i = 0; i < leftZeroIndex; i++)
            {
                a[i] = leftZeroIndex - i;
            }
            // fill in rightmost elements
            rightZeroIndex = indexes[numZeroes-1];
            for(int i = rightZeroIndex + 1; i < a.length; i++)
            {
                a[i] = i - rightZeroIndex;
            }
            //  now do the surfing
            for(int i = 0; i < numZeroes - 1; i++)
            {
                leftZeroIndex = indexes[i]+1;
                rightZeroIndex = indexes[i+1]-1;
                for(int j = 1; leftZeroIndex <= rightZeroIndex /* surfers collide */; j++)
                {
                    a[leftZeroIndex] = j;
                    a[rightZeroIndex] = j;
                    // surfers go towards each other
                    leftZeroIndex++;
                    rightZeroIndex--;
                }
            }
        }

[AssertNull]

Slight change of code to make the variable names better describe what is going on.

        //  now do the surfing
        for(int i = 0; i < numZeroes - 1; i++)
        {
            leftZeroIndex = indexes[i];
            rightZeroIndex = indexes[i+1];
            int leftSurferPosition = leftZeroIndex + 1;
            int rightSurferPosition = rightZeroIndex - 1;
            for(int j = 1; leftSurferPosition <= rightSurferPosition /* surfers collide */; j++)
            {
                a[leftSurferPosition] = j;
                a[rightSurferPosition] = j;
                // surfers go towards each other
                leftSurferPosition++;
                rightSurferPosition--;
            }
        }

[JamesCherrill]

The surfing is still a nested loop potentially with On^2 (depending on how many zeros there are). Similarly Adam and Danis solution is also potentially On^2

You can make one pass ascending and set each element to its distance from the previous zero, then a second pass descending overwriting any element whose distance from the previous zero is lower. Guaranteed On. I'll post code in a minute

[Adm666]

Hey Dani

counting from the left, as you are, and then store that number. Then, count from the right only up to the number we counted from the left. Once we hit it, we know that the left is closest, and we can just break.

i've just done exactly this right after i posted this, was kinda tired and didn't notice what im doing lol thanks alot though !

Hey AssertNull

Slight change of code to make the variable names better describe what is going on.

was alittle confused at first sight of the code but got it after a couple of times reading and tracking how it goes thank you so much
for guidance !
and the situation you've described, it may sound weird but it helped me put things in order with better understanding for arrays and fixing
my code thanks abunch ! appretiating you alot !

[JamesCherrill]

Unlike the other solutions this is guaranteed time complexity On, (additional) memory zero.

        int count = a.length; 
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0) {
                count = 0;
            } else {
                a[i] = ++ count;
            }
        }
        count = a.length;
        for (int i = a.length -1; i >=0; i--) {
            if (a[i] == 0) {
                count = 0;
            } else {
                count ++;
                if (a[i] > count) a[i] = count;
            }
        }

[Adm666]

Unlike the other solutions this is guaranteed time complexity On, (additional) memory zero.

you actually nailed it man ! i was working on running back and forth in the array. many thanks !

[AssertNull]

Thread is marked solved, but I have to disagree with this...

The surfing is still a nested loop potentially with On^2 (depending on how many zeros there are).

It's a nested loop, yes, but that does not make it On^2. If you look at the code, the nested loops partition the larger array rather than each nested looping through all n values. You iterate through the entire array once to find the zeroes. Then the "surfers" set the values. But note that the surfers' are territorial and respect each others' boundaries. They surf until they collide with another surfer as opposed to each surfing the whole array. If you look at each index of a[], it's being visited twice or three times total (one to test for zero in the initial sweep, once to set the value. A few indexes are set twice when the surfers actually collide). None of the n indexes will be visited anywhere close to n or even logn times no matter where the zeroes are.

[JamesCherrill]

<Started to write rubuttal, the realised AssertNull is right>

Yes, you're right
So all I'm claiming now is that my solution is simpler :)

JC