Skip to content

835. Image Overlap

https://leetcode.com/problems/image-overlap/

js
function maxOverlap(A, B) {
  const rows = A.length
  const cols = A[0].length
  let max_overlap = 0

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      const A_overlap = A.slice(i).map(r => r.slice(j))
      const B_overlap = B.slice(0, rows - i).map(r => r.slice(0, cols - j))

      let overlap = 0
      for (let x = 0; x < A_overlap.length; x++) {
        for (let y = 0; y < A_overlap[0].length; y++) {
          overlap += (A_overlap[x][y] & B_overlap[x][y])
        }
      }

      if (overlap > max_overlap) {
        max_overlap = overlap
      }
    }
  }

  return max_overlap
}

/**
 * @param {number[][]} A
 * @param {number[][]} B
 * @return {number}
 */
var largestOverlap = function(A, B) {
  return Math.max(maxOverlap(A, B), maxOverlap(B, A))
}
py
class Solution:

    def maxOverlap(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: int
        """
        rows = len(A)
        cols = len(A[0])
        max_overlap = 0

        for i in range(rows):
            for j in range(cols):
                A_overlap = [row[j:] for row in A[i:]]
                B_overlap = [row[:cols - j] for row in B[:rows - i]]
                overlap = [A_overlap[x][y] and B_overlap[x][y] for x in range(
                    len(A_overlap)) for y in range(len(A_overlap[0]))]
                overlap = sum(overlap)

                if overlap > max_overlap:
                    max_overlap = overlap

        return max_overlap

    def largestOverlap(self, A, B):
        return max(self.maxOverlap(A, B), self.maxOverlap(B, A))