Find minimum distance to reach nearest 0

Problem: Given a matrix of -1’s and 0’s, display matrix which contains minimum distance to reach nearest 0 for that particular position.
Example:
Input matrix:
-1 0 -1
-1 -1 -1
-1 -1 -1
Distance matrix:
1 0 1
2 1 2
3 2 3

Algorithm:

Let 'matrix' be the input 2-dimensional array which contains 0s and -1s. 
Let 'r' be the number of rows and 'c' be the  number of columns.

1. Create an output array to hold the distances of matrix elements from nearest 0.
Let distanceMatrix be the output array. Size of distanceMatrix would be same as matrix.
By default, all the elements of distanceMatrix are initialized to 0.

2. Find positions of all the 0s in matrix. Store these positions in a list.
Let 'positions' be the list which hold positions of all the 0s.

For every element in matrix
    if the element = 0
       add the position of the element in 'positions'
    End if
End for

3. Iterate over every element of matrix. If the element is not 0, 
then find nearest distance of the current element from 0.

for row = 0 to r-1, step row by 1
   for col = 0 to c-1, step col by 1
       // Find the shortest distance of current element from 0.
       distanceMatrix[row][col] = findShortestDistance (check step 4)
   End for
End for

4. Iterate over 'positions'
   Initialize shortest distance to a bigger value,
   say shortestDistance = Integer.Max

   For every 'position' in positions
      Find distance of current element from 0 using following formula
      distance = abs(x_coordinate_of_position - x_cordinate_of_current_element)
               + abs(y_coordinate_of_position - y_cordinate_of_current_element)
     
      if distance < shortestDistance
         shortestDistance = distance
      End if
   End for

   return shortestDistance

I hope algorithm is easy to understand.

Let us analyze above algorithm.
1. We find all the positions of zeros in input matrix. For this we iterate over all the elements of input matrix. So, complexity of this step is Ο(n).
2. To populate shortest distance in output matrix we iterate over all the elements of matrix. Say number of elements of the matrix be ‘n’. Then for every element, to find shortest distance we iterate over all the positions of 0. So if there are m occurrences of 0 in input matrix then, total run-time of this step is Ο(n * m).

So final run-time = Ο(n) + Ο(n * m) ≈ Ο(n * m).
(We ignore first Ο(n) as it lower order term.)

Java code:

In below code, we are using Position class. This class holds row and column index for a given number in the input matrix.

package com.javafries.matrix;

import java.util.ArrayList;
import java.util.List;

public class MatrixDistanceSolution {

	private static int[][] findDistanceMatrix(int[][] matrix) {
		List<Position> positions = findPositionsOfZero(matrix);

		int[][] distanceMatrix = new int[matrix.length][matrix[0].length];

		for (int row = 0; row < matrix.length; row++) {
			for (int col = 0; col < matrix[0].length; col++) {
				distanceMatrix[row][col] = getTheShortestDistance(row, col,
						positions);
			}
		}
		return distanceMatrix;
	}

	private static int getTheShortestDistance(int row, int col,
			List<Position> positions) {
		int shortestDistance = Integer.MAX_VALUE;
		for (Position position : positions) {
			int distance = Math.abs(row - position.getRowIndex())
					+ Math.abs(col - position.getColIndex());

			if (distance < shortestDistance)
				shortestDistance = distance;
		}
		return shortestDistance;
	}

	private static List<Position> findPositionsOfZero(int[][] matrix) {
		List<Position> positions = new ArrayList<Position>();

		int rowLen = matrix.length;
		int colLen = matrix[0].length;

		for (int row = 0; row < rowLen; row++) {
			for (int col = 0; col < colLen; col++) {
				if (matrix[row][col] == 0)
					positions.add(new Position(row, col));
			}
		}
		return positions;
	}

	private static void print(int[][] matrix) {
		int rowLen = matrix.length;
		int colLen = matrix[0].length;

		for (int i = 0; i < rowLen; i++) {
			for (int j = 0; j < colLen; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	private static class Position {
		int rowIndex;
		int colIndex;

		public Position(int rowIndex, int colIndex) {
			this.rowIndex = rowIndex;
			this.colIndex = colIndex;
		}

		public int getRowIndex() {
			return rowIndex;
		}

		public int getColIndex() {
			return colIndex;
		}
	}

	public static void main(String[] args) {
		int[][] matrix = { { -1, 0, -1 }, { -1, -1, -1 }, { -1, -1, -1 } };

		System.out.println("Input matrix: ");
		print(matrix);

		System.out.println("Distance matrix:");
		print(findDistanceMatrix(matrix));
	}
}

Output:

Input matrix: 
-1 0 -1 
-1 -1 -1 
-1 -1 -1 

Distance matrix:
1 0 1 
2 1 2 
3 2 3

I hope you understood the solution.
Your questions and comments are most welcome.

Leave a Reply