Question: Find a rectangle of 0s in matrix of 1s and 0s
Input:
|
1 2 3 4 5 6 7 8 9 10 |
{0,1,1,1,1,1,1}, {1,1,1,1,1,1,1}, {1,1,1,1,1,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,1,1,1,1}, {1,1,1,1,1,1,1} |
Output: [[0, 0], [0, 0], [3, 3], [7, 4]]
Solution:
Key to solve this question is to mark visited element as 1.
Usually, interviewer starts with a question where they ask you to assume just one rectangle. And once you implement it, they will ask you to modify it such that there might be multiple rectangles and return the array of all the co ordinates. So, make sure that whatever method you add at the start is easily extensible.
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 |
package interviewque; import java.util.ArrayList; import java.util.List; public class FindRectangles { public static List<Point> findRectangle(int matrix[][]) { List<Point> recCordinatesPoints = new ArrayList<Point>(); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if (matrix[i][j] == 0) { recCordinatesPoints.addAll(caputreCoordinates(matrix, i, j)); } } } return recCordinatesPoints; } public static List<Point> caputreCoordinates(int matrix[][], int i, int j) { int colStart = j; Point startPoint = new Point(i, j); while (j < matrix[0].length && matrix[i][j] == 0) { matrix[i][j] = 1; j++; } int colEnd = --j; i++; j = colStart; while (i < matrix.length && matrix[i][j] == 0) { while (j <= colEnd) { matrix[i][j] = 1; j++; } j = colStart; i++; } Point endPoint = new Point(--i, colEnd); List<Point> listPoint = new ArrayList<Point>(); listPoint.add(startPoint); listPoint.add(endPoint); return listPoint; } public static void main(String[] args) { int matrix[][] = { {0,1,1,1,1,1,1}, {1,1,1,1,1,1,1}, {1,1,1,1,1,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,0,0,1,1}, {1,1,1,1,1,1,1}, {1,1,1,1,1,1,1}}; System.out.println(findRectangle(matrix)); } } class Point { int x = -1; int y = -1; public Point(int x, int y) { this.x = x; this.y = y; } @Override public String toString() { return "[" + x + ", " + y + "]"; } } |
Complexity: O(row * column)
Git Url: FindRectangles.java