Problem 658. Find the biggest empty box

Created by Ned Gulley
Appears in Tough Stuff

Difficulty:Rate

Solve Later
Add To GroupÃ‚

You are given a matrix that contains only ones and zeros. Think of the ones as columns in an otherwise empty floor plan. You want to fit a big square into the empty space (denoted by zeros). What is the largest empty square sub-matrix you can find in the given matrix? You will return the row and column extent of the sub-matrix. The answer may not be unique. We will test that your sub-matrix is square, that it is empty, and that it contains the correct number of elements.
Example:
 Input a = [ 1 0 0 
             0 0 0 
             0 0 0 ]
 Output si = [ 2 3 2 3 ]
That is, the square indices are a(2:3,2:3). We verify that sum(sum(a(2:3,2:3))) is zero, and that it has four elements.

Solve

Solution Stats

2150 Solutions
488 Solvers

Last Solution submitted on Apr 04, 2025

Last 200 Solutions

Problem Comments

8 Comments

8 Comments

Show 5 older comments

Jerivington on 10 Jun 2016

Challenging like all the other problems set in the ASEE Challenge

jmac on 23 May 2020

Nice!

Dyuman Joshi on 9 Jul 2022

Test suite has been updated with unsymmetrical matrices.
The original problem description/statement doesn't mention any restriction on the input matrix size.