How many steps to the nearest zero value-CodePudding

Looking for some help with solving a seemingly easy algorithm.

Brief overview: We have an unsorted list of whole numbers. The goal is to find out how far each element of this list is from the nearest '0' value.

So if we have a list similar to this: [0, 1, 2, 0, 4, 5, 6, 7, 0, 5, 6, 9]

The expected result will be: [0, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3]

I've tried to simplify the problem in order to come up with some naive algorithm, but I can't figure out how to keep track of previous and next zero values. My initial thoughts were to figure out all indexes for zeros in the list and fill the gaps between those zeros with values, but this obviously didn't quite work out for me.

The poorly implemented code (so far I'm just counting down the steps to the next zero):

def get_empty_lot_index(arr: list) -> list:
    ''' Gets all indices of empty lots '''
    lots = []
    for i in range(len(arr)):
        if arr[i] == 0:
            lots.append(i)
    return lots

def space_to_empty_lots(arr: list) -> list:
    empty_lots = get_empty_lot_index(arr)
    new_arr = []
    start = 0
    for i in empty_lots:
        steps = i - start
        while steps >= 0:
            new_arr.append(steps)
            steps -= 1
        start = i   1
    return new_arr

CodePudding user response：

One possible algorithm is to make two sweeps through the input list: once forward, once backward. Each time retain the index of the last encountered 0 and store the difference. In the second sweep take the minimum of what was stored in the first sweep and the new result:

def space_to_empty_lots(arr: list) -> list:
    result = []
    # first sweep
    lastZero = -len(arr)
    for i, value in enumerate(arr):
        if value == 0:
            lastZero = i
        result.append(i - lastZero)
    # second sweep
    lastZero = len(arr)*2
    for i, value in reversed(list(enumerate(arr))):
        if value == 0:
            lastZero = i
        result[i] = min(result[i], lastZero - i)
    return result

NB: this function assumes that there is at least one 0 in the input list. It is not clear what the function should do when there is no 0. In that case this implementation will return a list with values greater than the length of the input list.