rects.js

const image1 = [
  [0,1,1,1,1,1],
  [1,1,1,0,0,1],
  [1,0,1,0,0,1],
  [1,0,1,1,1,1],
  [0,1,1,0,0,0],
]

// O( N * M )

// Memory = N * (M/2)

const findRectangles = (image) => {
  const rectangles = [];
  const openColumnRects = {};
  let lastOpenRect = null;
  
  image.forEach((row, y) => {
    let isOpenRow = false;

    row.forEach((cell, x) => {
      const openColumnRect = openColumnRects[x];
      
      switch (cell) {
        case 0:
          if (!isOpenRow && !openColumnRect) {
            const rect = { x, y, width: 1, height: 1 };
            rectangles.push(rect);
            openColumnRects[x] = rect;
            lastOpenRect = rect;
            isOpenRow = true;
            break;
          } 
          
          if (openColumnRect) {
            openColumnRect.height = openColumnRect.height + 1;
            lastOpenRect = openColumnRect;
            isOpenRow = true;
            break;
          }
          
          if (isOpenRow) {
            lastOpenRect.width = lastOpenRect.width + 1;
            break;
          }
          
          break;
          
        case 1:
        default:
          isOpenRow = false;
          lastOpenRect = null;
          
          if (openColumnRect) {
            openColumnRects[x] = null;
          }   
          break;
      }
    });
  });
  
  return rectangles;
}

console.log(findRectangles(image1))