1
$\begingroup$

My goal is to create a method that gets an array that only has 1's and 0's in it, and then turns every number into the amount of 'steps' it is away from the closest 0, left or right.

So for example [1] - [1] - [0] - [1] - [1] - [1] - [1] - [1] - [0] - [1] would be [2] - [1] - [0] - [1] - [2] - [3] - [2] - [1] - [0] - [1]

I also need to do it as simple as possible in terms of time and space complexity.

I'm not sure how to make it count how far a certain spot is from a 0 if it's from the right of the 0, or if there's another 0 nearby I'm not sure how to make it count which one is closest.

I'm assuming two for loops are needed?

Made a sketch: no idea if it makes sense.

 for (int i=0; i<a.length; i++)
{

    for (int j=i; j<a.length; j++)
    {
     if (a[j]==0)
      {
       if (i<j)
         {
           a[i]=j-i;
         }
        if(j<i)
         {  
           a[i]=i-j;
         }
       }
    }
 }
$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 4 '17 at 10:55
  • 1
    $\begingroup$ @Raphael It's actually O(n). two loops are not nested. (And I didn't want to give this info because it seems like OP is already almost on to it.) $\endgroup$ – Apiwat Chantawibul Feb 4 '17 at 11:11
  • 1
    $\begingroup$ All I see are some loops. Try to explain in words how you think you should proceed. The steps are: Understanding the problem. Figuring out how to solve it. Writing code. You left out the most important middle step. $\endgroup$ – gnasher729 Feb 4 '17 at 11:45
  • $\begingroup$ And two loops in the way you are using them are not needed. The problem can be solved easily in linear time. $\endgroup$ – gnasher729 Feb 4 '17 at 11:47
  • $\begingroup$ Since j starts at i then j cannot be < i $\endgroup$ – paparazzo Feb 4 '17 at 12:11
3
$\begingroup$

Let's try to solve a simpler problem first:

Given an array that only has 1's and 0's in it, the method turns every number into the amount of 'steps' it is away from the closest 0 to the left.

Now this problem is easy. A simple solution is: traverse the array from left to right, keeping track of the distance from the last zero encountered and updating each element with the distance.

A simple code:

dist = INF
for(i=0;i<a.length;i++){
    if(a[i] == 0)
       dist = 0;
    else
       dist++;
    b[i] = dist;
}

Now once you have solved the simpler problem for closest 0 to the left, you can similarly solve the problem for closest 0 to the right. With these two solutions, you should be able to easily get a solution for the original problem (by taking a min of the two solutions).

The solution evidently has O(n) time complexity, and can be easily coded to use only O(1) space by carefully manipulating the updates in the original array only.

$\endgroup$
2
$\begingroup$

Just some hints that will tell you how to solve it efficiently:

If you know where the first zero is, then you know what numbers to write down at all positions before and up to that zero. For example, if a [4] is the first zero, then you know the numbers for positions 0, 1, 2, 3 and 4 (4, 3, 2, 1, 0). You don't know the number for position 5 at this point.

If you know where two consecutive zeroes are, then you know what numbers to write down at all positions from the first to the second of these two zeroes. For example, if there is a zero at a [4] and the next zero is at a [9] then you know all the numbers for positions 4 to 9 (0, 1, 2, 2, 1, 0).

And if you know the position of the last zero, then you know what numbers to write down at all positions from that zero to the end of the array.

$\endgroup$
  • $\begingroup$ I think that's an overly complicated idea. $\endgroup$ – Raphael Feb 4 '17 at 13:18
-2
$\begingroup$

Just iterate in each direction and track the distance from the last zero

You could get fancier with some back tracking to only go one direction but would not be much faster

2n is still O(n)

lastZero is the distance from the last zero

int[] result  //this store the answer / calculation 
int lastZero = null
for(i = 0; i < len; i++)
{
    if(input[i] = 0)
    {
        lastZero = 0
        result[i] = 0
    }
    else if (lastZero != null)
    {
        lastZero++
        result[i] = lastZero
    }
}
//now go from right to left  
lastZero = null
for(i = len - 1; i <= 0; i--)
{
    if(input[i] = 0)
    {
        lastZero = 0
    }
    else if (lastZero != null)
    {
        lastZero++
        if(result[i] > lastZero or result[i] = null) 
           result[i] = lastZero
    }
}
$\endgroup$
  • 4
    $\begingroup$ Once again, we're looking for explanation, not code dumps. $\endgroup$ – David Richerby Feb 4 '17 at 12:44
  • $\begingroup$ @BDriz Input is your input array. Result is the array of results (calculation). $\endgroup$ – paparazzo Feb 4 '17 at 13:25
  • $\begingroup$ @Paparazzi No, I never claimed that it didn't work. That's now twice that you've mischaracterized what I said about that answer. $\endgroup$ – David Richerby Feb 4 '17 at 15:29
  • 1
    $\begingroup$ @Paparazzi A set of truths does not make a good answer. A single block of code certainly does not. $\endgroup$ – Raphael Feb 4 '17 at 16:15
  • 1
    $\begingroup$ It's okay if you write a block of code that solves it and there's an explanation attached. I'm just trying to learn and now I'm going through the logic of it. $\endgroup$ – B Driz Feb 4 '17 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.