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

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

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.

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.

`//Java Program to Find the Column with the Maximum Number of 1s in a Sorted Matrix`

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class ColumnWithMaxOne {

`// Function to print the column with maximum number of 1's.`

static void printColumn(int[][] matrix){

int i,j,columnnumber = -1;

int topmost = -1;

for(i=0;i<matrix.length;i++){

if(matrix[i][0] == 1)

`{`

columnnumber = 0;

topmost = i;

break;

`}`

`}`

if(topmost == -1){

topmost = matrix.length;

`}`

for(i=1; i<matrix.length; i++){

int x = topmost-1;

while(x >= 0 && matrix[i][x] == 1){

columnnumber = i;

topmost = x;

`x--;`

`}`

`}`

if(columnnumber != -1) {

System.out.println("Column with maximum number of One's in " +

"Sorted Matrix is");

for (i = 0; i < matrix[columnnumber].length; i++) {

System.out.print(matrix[columnnumber][i] + " ");

`}`

`}`

else{

System.out.println("There is no column containing 1's");

`}`

`}`

`// Function to read user input`

public static void main(String[] args) {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int rows,columns;

try{

System.out.println("Enter the number of rows");

rows = Integer.parseInt(br.readLine());

System.out.println("Enter the number of columns");

columns = Integer.parseInt(br.readLine());

`}`

catch(Exception e){

System.out.println("An error occurred");

return;

`}`

int[][] matrix = new int[rows][columns];

int i,j,prev;

prev=Integer.MIN_VALUE;

System.out.println("Enter the Sorted Matrix");

try{

for(i=0; i<rows; i++){

for(j=0; j<columns; j++){

matrix[i][j] = Integer.parseInt(br.readLine());

`}`

`}`

}catch (Exception e){

System.out.println("An error occurred");

return;

`}`

System.out.println("The matrix is");

for(i=0; i<rows; i++){

for(j=0; j<columns; j++){

System.out.print(matrix[i][j]);

`}`

System.out.println();

`}`

if(rows > 0 && columns >0)

printColumn(matrix);

`}`

`}`

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.

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

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.**

**Next Steps:**

- Get Free Certificate of Merit in Java Programming
- Participate in Java Programming Certification Contest
- Become a Top Ranker in Java Programming
- Take Java Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Buy Programming Books
- Buy Java Books
- Apply for Information Technology Internship
- Practice Programming MCQs
- Apply for Java Internship