Arrays: Fill binary matrix with 1's

rpanjrath · rpanjrath · commit d9b34849ed3c · 2014-02-18T14:21:48.000-08:00
diff --git a/README.md b/README.md
@@ -24,35 +24,39 @@ Arrays
 4.  Shift array of integers circularly given input array and shift size.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/circularshiftintarray/CircularShiftArray.java
 
-5.  Check if a sub-array exists in parent array.
+5.  Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true)
+    then make all the cells of ith row and jth column as 1.
+    Link:
+
+6.  Check if a sub-array exists in parent array.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/findarray/FindArrayImpl.java
 
-6.  Find duplicates count in sorted array.
+7.  Find duplicates count in sorted array.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/findduplicatecountsortedarray/DuplicatesCountInSortedArray.java
 
-7.  Write a program takes array input{1,0,2,3} and num = 3 and provides output {1,2}{0,3}{2,1}{3,0} sum equals the num.
+8.  Write a program takes array input{1,0,2,3} and num = 3 and provides output {1,2}{0,3}{2,1}{3,0} sum equals the num.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/findpairsequaltosum/FindPairsEqualToSum.java
 
-8.  Given a sorted array (ascending order and distinct elements), find i such that inputArr[i] = i. Return -1 if nothing found.
+9.  Given a sorted array (ascending order and distinct elements), find i such that inputArr[i] = i. Return -1 if nothing found.
     Link:
 
-9.  Find the contiguous subarray which has the largest sum. Kadane's algorithm.
+10. Find the contiguous subarray which has the largest sum. Kadane's algorithm.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/maxsubarray/FindMaxSubArray.java
 
-10. Given two sorted (ascending) arrays of integers, find the minimum difference between two integers in that array.
+11. Given two sorted (ascending) arrays of integers, find the minimum difference between two integers in that array.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/mindiffsortedarrays/MinimumDifferenceSortedArrays.java
 
-11. Print numbers with frequency.
+12. Print numbers with frequency.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/numberfrequency/PrintNumbersWithFrequency.java
 
-12. Find Number with Highest frequency in sorted array.
+13. Find Number with Highest frequency in sorted array.
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/numberwithhighestfreq/FindNumberWithHighestFreq.java
 
-13. Given an array, write a program to generate a random permutation of array elements.
+14. Given an array, write a program to generate a random permutation of array elements.
     Also asked as “shuffle a deck of cards” or “randomize a given array”.
     Link:
 
-14. Search for a number in rotated sorted array (Ascending or Descending).
+15. Search for a number in rotated sorted array (Ascending or Descending).
     Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/searchrotatedsortedarray/SearchInRotatedSortedArray.java
 
 
diff --git a/src/arrays/fillmatrixwithones/FillBinaryMatrixWithOnes.java b/src/arrays/fillmatrixwithones/FillBinaryMatrixWithOnes.java
@@ -0,0 +1,60 @@
+package arrays.fillmatrixwithones;
+
+/**
+ * Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true)
+ * then make all the cells of ith row and jth column as 1.
+ * User: techpanja
+ * Date: 2/8/14
+ * Time: 6:07 PM
+ */
+public class FillBinaryMatrixWithOnes {
+
+    private FillBinaryMatrixWithOnes() {
+
+    }
+
+    public static int[][] fillBinaryMatrix(int[][] matrix) {
+        int[] rowTemp = new int[matrix.length];
+        int[] colTemp = new int[matrix[0].length];
+        int noOfRows = rowTemp.length;
+        int noOfCols = colTemp.length;
+        if (noOfRows == 0 || noOfCols == 0) {
+            return new int[][]{};
+        }
+        for (int i = 0; i < noOfRows; i++) {
+            rowTemp[i] = 0;
+        }
+        for (int i = 0; i < noOfCols; i++) {
+            colTemp[i] = 0;
+        }
+        for (int i = 0; i < noOfRows; i++) {
+            for (int j = 0; j < noOfCols; j++) {
+                if (matrix[i][j] == 1) {
+                    rowTemp[i] = 1;
+                    colTemp[j] = 1;
+                }
+            }
+        }
+        for (int i = 0; i < noOfRows; i++) {
+            for (int j = 0; j < noOfCols; j++) {
+                if (rowTemp[i] == 1 || colTemp[j] == 1) {
+                    matrix[i][j] = 1;
+                }
+            }
+        }
+        return matrix;
+    }
+
+    public static void printMatrix(int[][] inputMatrix) {
+        for (int i = 0; i < inputMatrix.length; i++) {
+            for (int j = 0; j < inputMatrix[0].length; j++) {
+                System.out.print(inputMatrix[i][j] + " ");
+            }
+            System.out.println();
+        }
+    }
+
+    public static void main(String[] args) {
+        printMatrix(fillBinaryMatrix(new int[][]{{1, 0}, {0, 0}, {0, 0}}));
+    }
+}
