September LeetCoding Challenge, Day 6: Image Overlap

September 8, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 6 is Image Overlap. You’re given two images represented as binary, square matrices, of the same size. You want to translate one of the images by sliding it left, right, up or down any number of units such that, when placed on top of the other image, the number of 1s that overlap in both images is maximized. The length of the side of the images is at most 30.

The length of the side of the images is small enough for us to try all possible translations in $$\mathcal{O}(n^4)$$. The following is an implementation of that strategy: