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

«
»

This is the Java Program to Find the Column 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 column is sorted, print the first column with the maximum number of 1’s.
Example:
Matrix:
0 0 0 1
0 0 1 1
0 1 1 1
1 1 1 1

Output:
1 1 1 1

advertisement
Problem Solution

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

Program/Source Code

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

1. In function printColumn(), the variables columnnumber and topmost are initialized to -1.
2. The first loop for(i=0; i<matrix.length; i++), checks for 1 in first column,we set columnnumber to 0 and topmost to i if 1 exists.
3. Using the condition if(topmost == -1) we check if the first column is full of zeroes, in this case we set topmost to matrix.length;
4. The loop for(i=1; i<matrix.length; i++) is used to iterate through the remaining columns.
5. The nested loop while(x >= 0 && matrix[i][x] == 1), is used to check if the value in the current column, at a higher position is 1. If it is the variables topmost and columnnumber are updated. Here, variable x denotes the position and is initialised to topmost-1.
6. The condition if(columnnumber != -1) is used to display the column with maximum number of 1’s, if there is any, otherwise, a suitable message 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 - each column with different number of 1's):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Sorted Matrix
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1
The matrix is
0001
0011
0111
1111
Column with the maximum number of One's in Sorted Matrix is
1 1 1 1
 
Case 2 (Positive Test Case - two columns having same number of 1's):
 
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
0000
0011
0111
0111
Column with the maximum number of One's in Sorted Matrix is
0 1 1 1
 
Case 3 (Negative Test Case - no column containing 1):
 
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 column containing 1's

Sanfoundry Global Education & Learning Series – Java Programs.

Take Java Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
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.