Shortest path in matrix is to find the shortest distance from the the source to the destination. As you know, graph can be represented as adjacent matrix. Therefore, we can use the **Breadth First Search** algorithm in graph to solve this problem.

BFS starts from the source node. It explores all its adjacent nodes before going to the next level adjacent nodes. It is usually implemented with Queue. You visit each node in the queue until you find the destination. This question allows you to move in 4 directions, i.e, left, right, up and down. So, when visiting each node in queue, your next move is to visit cell’s 4 neighbors.

The trick about this question is that you are no only required to return shortest distance. You are also required to print the shortest path. The solution is to save the previous visited nodes in the cell object. At the end, you use linked list to track all nodes from destination to the source.

**Facebook Interview Question (CareerCup)**:

Given a MxN matrix where each element can either be 0 or 1. We need to print the shortest path between a given source cell to a destination cell. The path can only be created out of a cell if its value is 1.

public void print(int[][] matrix, int[] start, int[] end){

}

**Java Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
import java.util.LinkedList; public class MatrixPrintShortestPath { private static class Cell implements Comparable<Cell> { int x; int y; int dist; Cell prev; Cell(int x, int y, int dist, Cell prev) { this.x = x; this.y = y; this.dist = dist; this.prev = prev; } @Override public int compareTo(Cell o) { return dist - o.dist; } @Override public String toString(){ return "("+x+ ","+y+")"; } } //Time O(n^2), Space O(n^2) public static void print(int[][] matrix, int[] start, int[] end) { if (matrix[start[0]][start[1]] ==0 || matrix[end[0]][end[1]] ==0) return; Cell[][] cells = new Cell[matrix.length][matrix[0].length]; for (int i = 0; i < cells.length; i++) { for (int j = 0; j < cells[0].length; j++) { if (matrix[i][j] != 0) { cells[i][j] = new Cell(i, j, Integer.MAX_VALUE, null); } } } LinkedList<Cell> queue = new LinkedList<>(); Cell src = cells[start[0]][start[1]]; src.dist = 0; queue.add(src); Cell dest = null; Cell curr; while ((curr = queue.poll()) != null) { if (curr.x==end[0] && curr.y == end[1]) { dest = curr; } visit(cells, queue, curr.x - 1, curr.y, curr); visit(cells, queue, curr.x + 1, curr.y, curr); visit(cells, queue, curr.x, curr.y - 1, curr); visit(cells, queue, curr.x, curr.y + 1, curr); } if (dest == null) { return; } else { LinkedList<Cell> path = new LinkedList<>(); curr = dest; do { path.addFirst(curr); } while ((curr = curr.prev) != null); System.out.println(path); } } static void visit(Cell[][] cells, LinkedList<Cell> queue, int x, int y, Cell parent) { int dist = parent.dist + 1; if (x < 0 || x >= cells.length || y < 0 || y >= cells[0].length || cells[x][y] == null) { return; } Cell curr = cells[x][y]; if (dist < curr.dist) { curr.dist = dist; curr.prev = parent; queue.add(curr); } } public static void main(String[] args) { int[][] matrix = new int[][] { {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 0, 1}, {1, 0, 0, 0, 1, 1}, {1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0} }; int[] start = {2,4}; int[] end = {3,2}; print(matrix, start, end); } } |

**Output:**

[(2,4), (3,4), (3,3), (3,2)]

**O Notation:**

Time complexity: O(n^2)

Space complexity: O(n^2)

**Note:**

If you have any questions or want to put comments, please post at youtube. I will answer you!

**Action Items:**

Download ShortestPathBetweenCells.zip

Shortest path between cells in matrix tutorial

The complete list of coding interview questions