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

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.

```
 
```

//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);
```
```
    }
```
```
}
```

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.

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.

Note: Join free Sanfoundry classes at Telegram or Youtube

« Prev - Java Program to Print Odd Elements at Even Index

» Next - Smallest Sum Contiguous Subarray in Java

Related Posts:

Recommended Articles: