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 |
package com.ai1tutorial.ds.algo.matrix; public class RowWithMaxOneMatrix { public static void main(String[] args) { int matrix[][] = { { 0, 0, 1, 1, 1 }, { 0, 1, 1, 1, 1 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0 }, }; int resultIndex = rowWithMaxOneMatrix(matrix); if (resultIndex == -1) { System.out.println("There are no rows present with 1"); } else { System.out.println("Row number " + (resultIndex + 1) + " has the maximum number of 1s"); } } private static int rowWithMaxOneMatrix(int[][] matrix) { int noOfRows = matrix.length; int noOfCols = matrix[0].length; int rowIndex = 0; int currentMax = -1; int index; for (int i = 0; i < noOfRows; i++) { index = binarySearchFirstOne(matrix[i], 0, noOfCols - 1); if (index != -1 && noOfCols - index > currentMax) { currentMax = noOfCols - index; rowIndex = i; } } return rowIndex; } private static int binarySearchFirstOne(int[] arr, int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1) { return mid; } else if (arr[mid] == 0) { return binarySearchFirstOne(arr, mid + 1, high); } else { return binarySearchFirstOne(arr, low, mid - 1); } } return -1; } } |

1 |
Row number 2 has the maximum number of 1s |