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

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Maximum size of square sub-matrix with all 1s, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

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

  global cache
  if not cache:
    cache = [[None] * len(m[0]) for _ in range(len(m))]

  if not cache[i][j]:
    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:
      cache[i][j] = 0
    else:
      val = 1 + min(right, down, diagonal)
      mx[0] = max(mx[0], val)

      cache[i][j] = val

  return cache[i][j]

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])

// Javascript implementation

let cache = null;

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

  if (!cache) {
    cache = Array.from(Array(m.length), () => Array(m[0].length).fill(null));
  }

  if (!cache[i][j]) {
    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) {
      cache[i][j] = 0;
    } else {
      const val = 1 + Math.min(right, down, diagonal);
      max[0] = Math.max(max[0], val);
      m[i][j] = val;
    }
  }

  return m[i][j];
}

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]);

Maximum size of square sub-matrix with all 1s (Memoization)

Hint