When you're asked to mark an entire row and an entire column with 0's if an element of an MxN matrix is 0, here's my thought process:
The code below implements the solution: public static void setZeros(int[][] matrix) { #1) Define the contract of the function Name the function setZeros() to operate on a passed-in a 2-dimension int array, which will set all rows and columns of the matrix to zero if the element is 0. public static void setZeros(int[][] matrix) #2) Generic case algorithm Use a 2-passes scanning approach. The first pass scans through the entire int[][] matrix to see which row and column has 0. During the scan, on detecting element being 0, flag the corresponding rows/columns to indicate they have 0's. For storing the flags, introduce a int[] for flagging rows and another int[] for flagging columns. int[] row = new int[matrix.length]; The second pass scans through the entire int[][] matrix again to set the element to 0 if the corresponding row flag or column flag indicate the element should be set to 0.
The key concepts here are that int[][] is used to store the matrix, and utilizes a row array (int[]) and a column array (int[]) to store flags.
0 Comments
Leave a Reply. |
Categories
All
Archives
May 2020
|