[Leetcode]835. Image Overlap

Two images A and B are given, represented as binary, square matrices of the same size.  (A binary matrix has only 0s and 1s as values.)
We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image.  After, the overlap of this translation is the number of positions that have a 1 in both images.
(Note also that a translation does not include any kind of rotation.)
What is the largest possible overlap?
Notes: 
1 <= A.length = A[0].length = B.length = B[0].length <= 30
0 <= A[i][j], B[i][j] <= 1

This post will cover three approaches, especially the third one involves some tricks to make the programme shorter and fancier.

Brute force

Assuming the dimension of the matrix is n*n, we can exhaust all possible shifts (row\pmx,col\pmy), x \in (0...n) and y \in (0...n). Notably, For each shifting, we need to consider cases where moving A referring to B and moving B referring to A.

Time complexity would be O(n^4) as there are O(n^2) combinations of shifts and for each shift we take O(n^2) to find the overlaps.

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n = len(A)
        def count(x_offset,y_offset,M,R):
            cnt = 0
            # using enuermate() to generate two indices
            for r_row,m_row in enumerate(range(y_offset,n)):
                for r_col,m_col in enumerate(range(x_offset,n)):
                    cnt += M[m_row][m_col] == R[r_row][r_col] == 1
            return cnt
        ret = 0
        for y_offset in range(n):
            for x_offset in range(n):
                ret = max(ret,count(x_offset,y_offset,A,B),count(x_offset,y_offset,B,A))
        return ret

Optimized 1 – Hashmap

In the previous approach, we spent much time on scanning the entire matrix, which might waste too much time when processing sparse matrices. To improve it we can focus on 1-s in both matrices. When we try to find overlaps after shifting, we can instead look for cells from A and B such that they are all 1-s and they share the same shifts.

The maximum overlaps where cells share the same shifts.

We can implement this approach by finding all 1-s in both A and B and use the hashmap – with shifting vectors as the key – to count the number of cells that share the same shifts.

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n = len(A)
        def count_1(M):
            ret = []
            for r in range(n):
                for c in range(n):
                    if M[r][c] == 1:
                        ret.append((r,c))
            return ret
        dic = collections.defaultdict(int)
        max_overlap = 0
        A_1 = count_1(A)
        B_1 = count_1(B)
        for r_A,c_A in A_1:
            for r_B,c_B in B_1:
                vec = (r_A-r_B,c_A-c_B)
                dic[vec] += 1
                max_overlap = max(max_overlap,dic[vec])
        return max_overlap

Optimized 2 – 2-dimension key to 1-dimension key

Another great approach from @lee215, the logic is almost the same, but some tricks are applied:

  • Instead of iterating as for row in range(n) for col in range(n), we can iterate i in range(0,n*n) so the row is i//n and the col is i%n.
  • Instead of using (row,col) to record the positions, we can convert it into an integer rowcol. Normally row*n+col would work (n<=30 as shown in the question) but noticing that we are moving two directions – moving A referring to B and moving B referring to A, therefore col could be negative and there are cases when row*n+col cannot differentiate each case. For example, shifting 615 could be 20*30+15 or 21*30-15. Therefore we need at least row*2n+col. For simplicity, we can use 100 here as row*100+col.
class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n = len(A)
        A_1 = [i//n*100+i%n for i in range(n**2) if A[i//n][i%n]==1]
        B_1 = [i//n*100+i%n for i in range(n**2) if B[i//n][i%n]==1]
        c = collections.Counter(a-b for a in A_1 for b in B_1)
        return max(c.values() or [0])
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments