Question
Given a 2D array of 1s and 0s, find the largest square subarray of all 1s.
eg.
|
1 2 3 |
subarray([1, 1, 1, 0] [1, 1, 1, 1] [1, 1, 0, 0]) = 2 |
Once you think that you’ve solved the problem, click below to see the solution.
As always, remember that practicing coding interview questions is as much about how you practice as the question itself. Make sure that you give the question a solid go before skipping to the solution. Ideally if you have time, write out the solution first by hand and then only type it into your computer to verify your work once you've verified it manually. To learn more about how to practice, check out this blog post.
Solution
How was that problem? You can check out the solution in the video below.
Here is the source code for the solution shown in the video (Github):
|
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 |
// Brute force solution. From each cell see what is the biggest square // submatrix for which it is the upper left-hand corner public static int naiveSquareSubmatrix(boolean[][] arr) { int max = 0; // Compute recursively for each cell what it is the upper left corner of for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { if (arr[i][j]) max = Math.max(max, naiveSquareSubmatrix(arr, i, j)); } } return max; } // Overloaded recursive function private static int naiveSquareSubmatrix(boolean[][] arr, int i, int j) { // If we get to the bottom or right of the matrix, we can't go any // further if (i == arr.length || j == arr[0].length) return 0; // If the cell is False then it is not part of a valid submatrix if (!arr[i][j]) return 0; // Find the size of the right, bottom, and bottom right submatrices and // add 1 to the minimum of those 3 to get the result return 1 + Math.min(Math.min(naiveSquareSubmatrix(arr, i+1, j), naiveSquareSubmatrix(arr, i, j+1)), naiveSquareSubmatrix(arr, i+1, j+1)); } // Top down dynamic programming solution. Cache the values as we compute // them to avoid repeating computations public static int topDownSquareSubmatrix(boolean[][] arr) { // Initialize cache. Don't need to initialize to -1 because the only // cells that will be 0 are ones that are False and we want to skip // those ones anyway int[][] cache = new int[arr.length][arr[0].length]; int max = 0; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { if (arr[i][j]) max = Math.max(max, topDownSquareSubmatrix(arr, i, j, cache)); } } return max; } // Overloaded recursive function private static int topDownSquareSubmatrix(boolean[][] arr, int i, int j, int[][] cache) { if (i == arr.length || j == arr[0].length) return 0; if (!arr[i][j]) return 0; // If the value is set in the cache return it. Otherwise compute and // save to cache if (cache[i][j] > 0) return cache[i][j]; cache[i][j] = 1 + Math.min(Math.min(topDownSquareSubmatrix(arr, i+1, j, cache), topDownSquareSubmatrix(arr, i, j+1, cache)), topDownSquareSubmatrix(arr, i+1, j+1, cache)); return cache[i][j]; } // Bottom up solution. Start from the upper left-hand corner and compute // progressively larger submatrices public static int bottomUpSquareSubmatrix(boolean[][] arr) { int max = 0; // Initialize cache int[][] cache = new int[arr.length][arr[0].length]; // Iterate over the matrix to compute all values for (int i = 0; i < cache.length; i++) { for (int j = 0; j < cache[0].length; j++) { // If we are in the first row or column then the value is just // 1 if that cell is true and 0 otherwise. In other rows and // columns, need to look up and to the left if (i == 0 || j == 0) { cache[i][j] = arr[i][j] ? 1 : 0; } else if (arr[i][j]) { cache[i][j] = Math.min(Math.min(cache[i][j-1], cache[i-1][j]), cache[i-1][j-1]) + 1; } if (cache[i][j] > max) max = cache[i][j]; } } return max; } |
Did you get the right answer to this coding interview question? Please share your thoughts in the comments below.
