- How to fill the auxiliary matrix?
- Create an auxiliary array of the same size as given input array. We will fill the auxiliary array with Maximum size square sub-matrix with all 1’s possible with respect to the particularity cell.
- Once the auxiliary is fill, scan it and find out the maximum entry in it, this will the size of Maximum size square sub-matrix with all 1’s in the given matrix.
- Copy the first row and first column from the given array to auxiliary array.
- For filling rest of cells, check if particularity cell’s value is 0 in given array, if yes then put 0 against to that cell in auxiliary array.
- check if particularity cell’s value is 1 in given array, if yes then put Minimum (value in the left cell, top cell and left-top diagonal cell) + 1 in auxiliary cell.
- Logic of auxiliary matrix?
- Where the position of 1 is matched then go to
- minimum of this position data by using and adding plus 1
- auxiliaryMatrix[i][j] = min(auxiliaryMatrix[i - 1][j - 1],auxiliaryMatrix[i][j - 1],auxiliaryMatrix[i - 1][j]) + 1;
-
010101101010011110001110111111Base Matrix010101101010011110001110111111Out Put Matrix of color red010101101010011110001220111231Auxiliary Matrix010101101010011110001220111231Auxiliary Matrix sub set select
package com.kartik.matrix;public class MaxSquareSubMatrix { /** * * @param matrixInput * arrA * @param row * row * @param cols * cols */ public void displayMatrix(int[][] matrixInput, int row, int cols) { for (int i = 0; i < row; i++) { for (int j = 0; j < cols; j++) { System.out.print(matrixInput[i][j] + " "); } System.out.println(); } } /** * @purpose This is find out the Square sub matrix * @param baseMatrixInput * arrA * @param row * row * @param cols * cols */ public void subMatrix(int[][] baseMatrixInput, int row, int cols) { System.out.println("Display base of matrix"); displayMatrix(baseMatrixInput, row, cols); int maxSizeOfMatrix, maxRow, maxCol; int[][] auxiliaryMatrix = new int[row][cols]; // copy the first row for (int i = 0; i < cols; i++) { auxiliaryMatrix[0][i] = baseMatrixInput[0][i]; } // copy the first column for (int i = 0; i < row; i++) { auxiliaryMatrix[i][0] = baseMatrixInput[i][0]; } // for rest of the matrix check if arrA[i][j]==1 System.out.println("----------Start---------------"); createAuxiliaryMatrix(baseMatrixInput, row, cols, auxiliaryMatrix); System.out.println("----------End---------------"); System.out.println("Display auxiliary matrix"); displayMatrix(auxiliaryMatrix, row, cols); // find the maximum size of sub matrix maxSizeOfMatrix = auxiliaryMatrix[0][0]; maxRow = 0; maxCol = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < cols; j++) { if (auxiliaryMatrix[i][j] > maxSizeOfMatrix) { maxSizeOfMatrix = auxiliaryMatrix[i][j]; maxRow = i; maxCol = j; } } } System.out.println("Maximum size square sub-matrix with all 1s: " + maxSizeOfMatrix); System.out.println("Display of the sub matrix"); displaySubMatrix(maxSizeOfMatrix, maxRow, maxCol, auxiliaryMatrix); System.out.println("Display of the sub matrix position"); displayPositionOfSubMatrix(maxSizeOfMatrix, maxRow, maxCol); } /** * * @param baseMatrixInput * @param row * @param cols * @param auxiliaryMatrix */ private void createAuxiliaryMatrix(int[][] baseMatrixInput, int row, int cols, int[][] auxiliaryMatrix) { for (int i = 1; i < row; i++) { for (int j = 1; j < cols; j++) { if (baseMatrixInput[i][j] == 1) { // +1 is for increment because new formating of matrix like // [[0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0], [0, 1, 1, 1, 1, // 0], [0, 0, 1, 2, 2, 0], [1, 1, 1, 2, 3, 1]] //create your own minimum function or use Math.min function like this /*auxiliaryMatrix[i][j] = Math.min( auxiliaryMatrix[i - 1][j - 1], Math.min( auxiliaryMatrix[i][j - 1], auxiliaryMatrix[i - 1][j])) + 1;*/ System.out.println(i+""+j+"-->"+(i - 1)+""+(j - 1)+" , "+i+""+(j-1)+" , "+(i-1)+""+j); auxiliaryMatrix[i][j] = min(auxiliaryMatrix[i - 1][j - 1],auxiliaryMatrix[i][j - 1],auxiliaryMatrix[i - 1][j]) + 1; } else { auxiliaryMatrix[i][j] = 0; } } } } /** * @purpose This is display of matrix data in reverser order * @param maxSizeOfMatrix * @param maxRow * @param maxCol * @param auxiliaryMatrix */ private void displaySubMatrix(int maxSizeOfMatrix, int maxRow, int maxCol, int[][] auxiliaryMatrix) { for (int i = maxRow; i > maxRow - maxSizeOfMatrix; i--) { for (int j = maxCol; j > maxCol - maxSizeOfMatrix; j--) { System.out.print(auxiliaryMatrix[i][j] + " "); } System.out.println(); } } /** * @purpose This is display of matrix position where this matrix generated * in reverse order * @param maxSizeOfMatrix * @param maxRow * @param maxCol */ private void displayPositionOfSubMatrix(int maxSizeOfMatrix, int maxRow, int maxCol) { for (int i = maxRow; i > maxRow - maxSizeOfMatrix; i--) { for (int j = maxCol; j > maxCol - maxSizeOfMatrix; j--) { System.out.print(i + "" + j + ","); } System.out.println(); } } /** * * @param a * @param b * @param c * @return */ int min(int a, int b, int c) { int m = a; if (m > b) m = b; if (m > c) m = c; return m; } public static void main(String[] args) { int[][] twoDimensionalMatrix = { { 0, 1, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0 }, { 0, 1, 1, 1, 1, 0 }, { 0, 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1, 1 } }; /*int[][] twoDimensionalMatrix = { {0 , 1 , 1, 0, 1 }, { 1 , 1 , 0 , 1 , 0 }, { 0, 1 ,0, 1, 0 }, { 1 , 1, 1 , 1 , 0 }, { 1 , 1 , 1, 1 , 1 },{0 , 1 , 1, 1 , 1} };*/ MaxSquareSubMatrix baseMatrix = new MaxSquareSubMatrix(); baseMatrix.subMatrix(twoDimensionalMatrix, 5, 6); } }Out put:Display base of matrix0 1 0 1 0 11 0 1 0 1 00 1 1 1 1 00 0 1 1 1 01 1 1 1 1 1----------Start---------------12-->01 , 11 , 0214-->03 , 13 , 0421-->10 , 20 , 1122-->11 , 21 , 1223-->12 , 22 , 1324-->13 , 23 , 1432-->21 , 31 , 2233-->22 , 32 , 2334-->23 , 33 , 2441-->30 , 40 , 3142-->31 , 41 , 3243-->32 , 42 , 3344-->33 , 43 , 3445-->34 , 44 , 35----------End---------------Display auxiliary matrix0 1 0 1 0 11 0 1 0 1 00 1 1 1 1 00 0 1 2 2 01 1 1 2 3 1Maximum size square sub-matrix with all 1s: 3Display of the sub matrix3 2 12 2 11 1 1Display of the sub matrix position44,43,42,34,33,32,24,23,22,
Example:
I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.