Java Program to Find the Row with Maximum Number of 1s

«
»

This is the Java Program to Find the Row with the Maximum Number of 1’s in a Sorted Matrix.

Problem Description

Given a boolean matrix of 0’s and 1’s, where each row is sorted, print the row first with the maximum number of 1’s.
Example:
Matrix:
0 0 1 1
0 0 1 1
0 1 1 1
0 0 1 1

Output:
0 1 1 1

advertisement
Problem Solution

Iterate through the first row to find the index of the leftmost one in it. For each of the next row, if the element at the index before the leftmost one is zero, then skip that row, otherwise update the index for leftmost one.

Program/Source Code

Here is the source code of the Java Program to Find the Row with the Maximum Number of 1’s in a Sorted Matrix. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Find the Row with the Maximum Number of 1's in a Sorted Matrix
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class RowWithMaxOne {
  8.     // Function to find and display the row with maximum number of 1's
  9.     static void printRow(int[][] matrix) {
  10.         int i, j, rownumber = -1;
  11.         int leftmost = -1;
  12.         for (i = 0; i < matrix[0].length; i++) {
  13.             if (matrix[0][i] == 1) {
  14.                 rownumber = 0;
  15.                 leftmost = i;
  16.                 break;
  17.             }
  18.         }
  19.         if (leftmost == -1) {
  20.             leftmost = matrix[0].length;
  21.         }
  22.         for (i = 1; i < matrix[0].length; i++) {
  23.             int x = leftmost - 1;
  24.                 while (x >= 0 && matrix[i][x] == 1) {
  25.                     rownumber = i;
  26.                     leftmost = x;
  27.                     x--;
  28.                 }
  29.          }
  30.             if (rownumber != -1) {
  31.                 System.out.println("Row with maximum number of" +
  32.                                       "One's in Sorted Matrix is");
  33.                 for (i = 0; i < matrix[rownumber].length; i++) {
  34.                     System.out.print(matrix[rownumber][i] + " ");
  35.                 }
  36.             } else {
  37.                 System.out.println("There is no row containing 1's");
  38.             }
  39.     }
  40.     //Main Function to read input
  41.     public static void main(String[] args) {
  42.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  43.         int rows,columns;
  44.         try{
  45.             System.out.println("Enter the number of rows");
  46.             rows = Integer.parseInt(br.readLine());
  47.             System.out.println("Enter the number of columns");
  48.             columns = Integer.parseInt(br.readLine());
  49.         }
  50.         catch(Exception e){
  51.             System.out.println("An error occurred");
  52.             return;
  53.         }
  54.         int[][] matrix = new int[rows][columns];
  55.         int i,j,prev;
  56.         prev=Integer.MIN_VALUE;
  57.         System.out.println("Enter the Boolean Matrix");
  58.         try{
  59.             for(i=0; i<rows; i++){
  60.                 for(j=0; j<columns; j++){
  61.                     matrix[i][j] = Integer.parseInt(br.readLine());
  62.                 }
  63.             }
  64.         }catch (Exception e){
  65.             System.out.println("An error occurred");
  66.             return;
  67.         }
  68.         System.out.println("The matrix is");
  69.         for(i=0; i<rows; i++){
  70.             for(j=0; j<columns; j++){
  71.                 System.out.print(matrix[i][j]);
  72.             }
  73.             System.out.println();
  74.         }
  75.         if(rows > 0 && columns > 0)
  76.         printRow(matrix);
  77.     }
  78. }
Program Explanation

1. In function printRow(), the loop for (i = 0; i < matrix[0].length; i++), iterates through the first row and finds the index of the leftmost one.
2. If there is no one in the first row, then the variable leftmost is set equal to the number of columns.
3. The loop for (i = 1; i < matrix[0].length; i++) traverses through the remaining rows.
4. The variable x is set to leftmost-1 and the nested loop while (x >= 0 && matrix[i][x] == 1) is used to find the index of the leftmost 1 in the current row.
5. Finally, the row with maximum number of 1’s is displayed.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Time Complexity: O(n+m) where n is the number of rows and m is the number of columns in the matrix respectively.

Runtime Test Cases
 
Case 1 (Positive Test Case):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Boolean Matrix
1
1
1
1
0
0
0
1
0
0
1
1
0
1
1
1
The matrix is
1111
0001
0011
0111
Row with the maximum number of One's in Sorted Matrix is
1 1 1 1 
 
Case 2 (Positive Test Case - another example):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Boolean Matrix
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
The matrix is
0001
0011
0111
0011
Row with the maximum number of One's in Sorted Matrix is
0 1 1 1
 
Case 3 (Negative Test Case):
 
Enter the number of rows
3
Enter the number of columns
3
Enter the Boolean Matrix
0
0
0
0
0
0
0
0
0
The matrix is
000
000
000
There is no row containing 1's

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.