Maximum size of square sub-matrix with all 1s

Given a binary matrix of size n * m, find out the maximum size of square sub-matrix with all 1s.

Hint

The algorithm examines each position (i, j) within the given matrix. Explores three possible paths:

• Right: Check size to the right of the current position.
• Bottom: Check size below the current position.
• Diagonal: Check size diagonally down and to the right.

If the value at the current position (i, j) is 0, it returns 0 (meaning it won't be part of result sub-matrix). Return take the minimum size of these three paths after add 1 to it. Compares this size to the max size found so far. After examining all positions in the matrix, returns the max size of the square sub-matrix with all 1s.

• Python
• Javascript
•  Run

def search(m, i, j, mx):
  if i < 0 or i >= len(m) or j < 0 or j >= len(m[0]):
    return 0

  right = search(m, i, j + 1, mx)
  down = search(m, i + 1, j, mx)
  diagonal = search(m, i + 1, j + 1, mx)

  if m[i][j] == 0:
    return 0

  val = 1 + min(right, down, diagonal)
  mx[0] = max(mx[0], val)

  return val

data = [
  [0, 1, 1, 0, 1],
  [1, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
  [1, 1, 1, 1, 0],
  [1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0]
]

mx = [0]

search(data, 0, 0, mx)

print(mx[0])

function search(m, i, j, max) {
  if (i < 0 || i >= m.length || j < 0 || j >= m[0].length) {
    return 0;
  }

  let right = search(m, i, j + 1, max);
  let down = search(m, i + 1, j, max);
  let diagonal = search(m, i + 1, j + 1, max);

  if (m[i][j] === 0) return 0;

  let val = 1 + Math.min(right, down, diagonal);
  max[0] = Math.max(max[0], val);

  return val;
}

const data = [
  [0, 1, 1, 0, 1],
  [1, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
  [1, 1, 1, 1, 0],
  [1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0]
];

let max = [0];

search(data, 0, 0, max);

console.log(max[0]);