Blog

Find if there is a rectangle in binary matrix with corners as 1.

Input: mat[][] = {{1, 0, 0, 1, 0}, {0, 0, 1, 0, 1}, {0, 0, 0, 1, 0}, {1, 0, 1, 0, 1}}
Output: YES
Note: as there exists – 
           1 0 1
           0 1 0
           1 0 1

public class CheckRectangle {
	static boolean isValidRectangel(int mat[][]) {
		int row = mat.length;
		if (row == 0)
			return false;
		int column = mat[0].length;

		for (int i = 0; i < row; i++)
			for (int j = 0; j < column; j++)

				if (mat[i][j] == 1) {
					for (int k = i + 1; k < row; k++)
						for (int l = j + 1; l < column; l++)
							if (mat[i][l] == 1 && mat[k][j] == 1 && mat[k][l] == 1)
								return true;
				}
		return false;
	}

	public static void main(String[] args) {
		int mat[][] = { { 1, 0, 0, 1, 0 }, { 0, 0, 1, 0, 1 }, { 0, 0, 0, 1, 0 }, { 1, 0, 1, 0, 1 } };
		if (isValidRectangel(mat)) {
			System.out.print("YES");

		} else {
			System.out.print("NO");
		}

	}

}

Thanks and Regards,
Solution provided by Nilmani Prashanth