instagram

Maximum size square sub-matrix with all 1s or 0s

by omt

Given a matrix of dimensions mxn having all entries as 1 or 0, find out the size of maximum size square sub-matrix with all 1s or 0s.

Input :

static int a[][] = { //
			{ 0, 1, 1, 0, 1, 1 }, //
			{ 1, 1, 0, 1, 1, 1 }, //
			{ 0, 1, 1, 1, 0, 0 }, //
			{ 1, 1, 1, 1, 0, 0 }, //
			{ 1, 1, 1, 1, 1, 0 }, //
			{ 0, 1, 1, 1, 0, 1 },//
	};

Output :

Max square size for 1 is :3
Max square size for 0 is :2

Algorithm

package com.omt.learn.algo;

public class MaxSizeSquareInMatrix {

	static int a[][] = { //
			{ 0, 1, 1, 0, 1, 1 }, //
			{ 1, 1, 0, 1, 1, 1 }, //
			{ 0, 1, 1, 1, 0, 0 }, //
			{ 1, 1, 1, 1, 0, 0 }, //
			{ 1, 1, 1, 1, 1, 0 }, //
			{ 0, 1, 1, 1, 0, 1 },//
	};

	static int b[][] = { //
			{ 0, 1, 1, 0, 0, 0 }, //
			{ 1, 1, 0, 0, 0, 0 }, //
			{ 0, 1, 1, 0, 0, 0 }, //
			{ 1, 1, 1, 1, 0, 0 }, //
			{ 1, 1, 1, 1, 1, 0 }, //
			{ 0, 1, 1, 1, 0, 1 },//
	};

	static int c[][] = { //
			{ 0, 1, 1, 0, 0, 0 }, //
			{ 1, 1, 0, 0, 1, 0 }, //
			{ 0, 1, 1, 0, 0, 0 }, //
			{ 1, 1, 1, 1, 0, 0 }, //
			{ 1, 1, 0, 1, 1, 0 }, //
			{ 0, 1, 1, 1, 0, 1 },//
	};

	static int d[][] = { //
			{ 0, 1, 1, 0, 0, 0 }, //
			{ 1, 1, 0, 0, 1, 0 }, //
			{ 0, 0, 1, 0, 1, 0 }, //
			{ 1, 1, 1, 1, 0, 0 }, //
			{ 1, 0, 0, 1, 1, 0 }, //
			{ 0, 1, 1, 1, 0, 1 },//
	};

	public static void main(String[] args) {

		System.out.println("Max square size for 1 is :" + findMaxSquareSize(1, a));
		System.out.println("Max square size for 0 is :" + findMaxSquareSize(0, a));

		System.out.println("Max square size for 1 is :" + findMaxSquareSize(1, b));
		System.out.println("Max square size for 0 is :" + findMaxSquareSize(0, b));

		System.out.println("Max square size for 1 is :" + findMaxSquareSize(1, c));
		System.out.println("Max square size for 0 is :" + findMaxSquareSize(0, c));

		System.out.println("Max square size for 1 is :" + findMaxSquareSize(1, d));
		System.out.println("Max square size for 0 is :" + findMaxSquareSize(0, d));

	}

	public static int findMaxSquareSize(int squareFor, int[][] matrix) {
		int maxSize = 0;

		int[][] temp = new int[matrix.length][matrix.length];

		for (int i = 0; i < matrix.length; i++) {
			if (matrix[0][i] == squareFor) {
				temp[0][i] = 1;
			}

			if (matrix[i][0] == squareFor) {
				temp[i][0] = 1;
			}
		}

		for (int i = 1; i < matrix.length; i++) {
			for (int j = 1; j < matrix.length; j++) {
				if (matrix[i][j] == squareFor) {
					int size = 1 + Math.min(temp[i - 1][j], Math.min(temp[i - 1][j - 1], temp[i][j - 1]));
					temp[i][j] = size;
					if (maxSize < size) {
						maxSize = size;
					}
				}
			}
		}

		return (maxSize > 1 ? maxSize : 0);
	}

}
Share