Facebook Phone screen for E6
Anonymous User
1462

Given a 2D matrix that has 2K ones. Find K paths that connect two 1's and you can move up, down, right or left. These paths should be non intersecting.

1000
0000
0001

Path = [[0,0],[0,1],[0,2],[0,3],[1,3],[2,3]]

If there are 4 1s, we need to print two non intersecting paths.

I did in O(MN) time complexity.

List<List<Node>> findPaths(int[][] mat) {
List<List<Node>> res = new ArrayList<>();

for (int r = 0; r < mat.length; r++) {
  for (int c = 0; c < mat[0].length; c++) {
    if (mat[r][c] == 1) {
      List<Node> tt = new ArrayList<>();
      findPath(mat, r, c, tt, r, c);
      res.add(tt);
    }
  }
}

return res;
}

  boolean findPath(int[][] mat, int r, int c, List<Node> res, int or, int oc) {
  if (r < 0 || c < 0 || r >= mat.length || c >= mat[0].length || mat[r][c] == 2) {
   return false;
  }

res.add(new Node(r, c));
if ((r != or || c != oc) && mat[r][c] == 1) {
  mat[r][c] = 2;
  return true;
}

mat[r][c] = 2;

if (findPath(mat, r - 1, c, res, or, oc)) {
  return true;
}

if (findPath(mat, r + 1, c, res, or, oc)) {
  return true;
}

if (findPath(mat, r, c - 1, res, or, oc)) {
  return true;
}

if (findPath(mat, r, c + 1, res, or, oc)) {
  return true;
}

res.remove(res.size()-1);
return false;

}

Comments (3)