CareerCup

We need to provide largest submatrix not largest square submatrix. Hence we need to check all sub-matrixes possible and it can be done by
geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

I thought the same as ninhnnsoc except for the case that returns the whole matrix itself.
Assumption is that you need to return the sub matrix (that is smaller than whole matrix) that has most 1s.

1. Scan each row in the matrix and store the rows that has no 1 in the array.
2. Check the array to see if there are any row having no 1.
3. If array is empty, compare the number of 1s in the four cases:
case 1. count number of 1s for Matrix M-1 X N staring from 0,0
case 2. count number of 1s for Matrix M-1 X N starting from 1,0
case 3. count number of 1s for Matrix M X N-1 starting from 0,0
case 4. count number of 1s for Matrix M X N-1 starting from 0,1
4. returns the matrix with most 1s
5. if array is not empty, divide MxN into sub matrices and count number of the 1s
6. Returns the matrix with most 1s

If there is no row with all 0s, then the whole matrix is the biggest sub matrix with maximum number of 1's (as per the definition of subset)
Otherwise,
the max submatrix with max 1s is

[0,0] to [1st row of zeros-1], max col] OR
[1st row of zeros+1, 0] to [2nd row of zeros-1, max_col]
...
[last row of zeros+1, 0] to [max row, max col]

Which means, number of columns will never reduce.

This can be solved by using sum of 1s in each row.
1. Create an array of sums of each row
2. If there is no 0 entry in this array of sums, return [0][0] - [max row][max][col]
3. If there are one or more 0 entries in this array of sums, find the sum of each sub array separated by 0s.
4. Return the sub matrix as [previous entry of 0's +1][0] - [next entry of 0's - 1][max col]
5. The return will have to take care of 0th and last rows. It can be achieved by initializing previous to -1 and next to max row +1

Can you provide some more details. As in - any ratio that needs to be maintained ?

If this is the question then my ans is -

Step 1 : Consider m*n matrix A[M][N]
Step 2 : Find the sum of all the rows and store it in a map sum[row_number, sum]
Step 3 : As mentioned, there can be rows with 0 values, find the rows which maximum sum of values between two zeros(as we don't need to include rows with 0 values)
Step 4 : If there are no zero rows or only one zero row then find the smallest sum in the map and then you can get the array with maximum one's
Step 5: You can further iterate on the result to remove columns.

Let me know whatever your views are.

If each row of the input matrix has at least one 1 already, then I will output the whole matrix as the answer, since it is the largest submatrix satisfied the constraint.

If there are rows that have zero number of 1: I "slice" the matrix by these zero rows, and find the answer among the resulting sliced submatrices.

Does it answer the question?

Scan each row and create a 1-dimensional array of count of 1's in each row. This will result in something like below:
1 2 11 0 4 5 2 8 0 1 9 7 9 0 16
The size of this array is the number of rows in the matrix and the index of each item is the row index of the original MxN matrix. Now, the problem boils down to finding the "Maximum subarray problem" with one restriction - the subarray should not be the whole array itself.

obviously the matrix itself will give that submatrix which has most number of 1s (if all row contains at least one 1). We can break the matrix in those submatrix which comes before or after a row such that the row contains all zero..
I guess this question on geeksforgeeks
geeksforgeeks/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
is different from what it is asked.. Please Correct me if i am wrong..

public static void main(String[] args) {
		int[][] a = { { 0, 0, 0, 0 }, { 0, 0, 1, 1 }, { 0, 0, 1, 1 } };
		int subRowStrtIdx = 0;
		int subColStrtIdx = 0;
		int subRowEndIdx = a.length;
		int subColEndIdx = a[0].length;
		int tmp = 0;
		int cnt = 0;

		for (int i = 0; i < a[0].length; i++) { // col

			for (int j = 0; j < a.length; j++) { // row

				if (a[j][i] != 1) {
					++cnt;
				}
			}
			if (cnt == a.length) {
				subRowStrtIdx = tmp++;
				subRowEndIdx = a.length;
				subColStrtIdx = i + 1;
				subColEndIdx = a[0].length;
			}
			cnt = 0;
		}
		System.out.println("[" + subRowStrtIdx + " " + subColStrtIdx + "] ["
				+ subRowEndIdx + " " + subColEndIdx + "]");

	}

public class SubMtrix {

	private int m =3;
	private int n =4;
	private int mark_i = 0,mark_another=0;
	private int part_row = 0;
	private int row_1 = 0,row_2 =0;;
	private int end_row =0,end_another=0;
	public static void main(String args[]) {
		int [][] a ={ { 0, 1,1,0}, { 0,0,0,0}, { 1, 1, 0, 0 } };
		SubMtrix sm = new SubMtrix();
		 sm.subMat(a);
		
		
	}
	public  void subMat(int a[][]) {
		for(int i =0 ;i < a.length;i++){
			part_row = 0;
			for(int j =0;j < a[0].length;j++) {
				if(a[i][j]==1){
					
					if(row_1 == 0)
					     mark_i = i;
					part_row++;
					row_1++;
					end_row =i+1;
					
					
				}
			}
			if(part_row ==0)
			{
				row_2=row_1;
				mark_another = mark_i;
				end_another = end_row;
				
				row_1 =0;
			}
			if(part_row !=0 & row_2 < row_1){
				row_2 =row_1;
				mark_another = mark_i;
				end_another = end_row;
			}
		}
		for(int i = mark_another;i < end_another;i++){
			for(int j =0;j < n;j++) {
				System.out.print(a[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	
	
}

Given an NxM matrix that contains only 0s and 1s, find out the size of the maximum square sub-matrix with all 0s. You need to return the size of the square matrix with all 0s.
Input format :
The first line of the test case contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively.

Second-line onwards, the next 'N' lines or rows represent the ith row values.

Each of the ith rows constitutes column values separated by a single space (Either 0 or 1).
Output Format:
Print the size of maximum square sub-matrix.
Constraints :
0 <= N <= 10^4
0 <= M <= 10^4

Time Limit: 1 sec
Sample Input 1:
3 3
1 1 0
1 1 1
1 1 1
Sample Output 1:
1
Sample Input 2:
4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Sample Output 2:
4

Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]

Algorithm mentioned in this link can be applied - >

geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/