The trick is to stop thinking about the grid and start thinking about shifts. Every way I could slide `img1` onto `img2` is just a translation vector `(dr, dc)`, and the overlap it produces is the number of `1`-cells that line up under that shift. So instead of trying shifts, I let the shifts declare themselves. The naive instinct is to loop over all `(2n-1)^2` possible translations and, for each, sweep the whole `n x n` grid counting matches. That works for `n <= 30` but it wastes time on shifts that no `1`-cell ever needs. The better move: collect the coordinates of every `1` in each image, and for each pair (one cell from `img1`, one from `img2`) record the single shift `(q.r - p.r, q.c - p.c)` that would map the first onto the second. Tally those shifts; the most frequent one is the answer, because each occurrence is exactly one pair of `1`s that coincide after that translation. ### Worked example Take `img1 = [[1,1,0],[0,1,0],[0,1,0]]` and `img2 = [[0,0,0],[0,1,1],[0,0,1]]`. The `1`s in `img1` sit at `(0,0), (0,1), (1,1), (2,1)`; in `img2` at `(1,1), (1,2), (2,2)`. Focus on the shift `(dr,dc) = (1,1)`: `(0,0)->(1,1)` ✓, `(0,1)->(1,2)` ✓, `(1,1)->(2,2)` ✓. Three pairs vote for `(1,1)`, and no shift beats it, so the answer is `3` — slide `img1` down one and right one. ### Complexity - Time O(n^4) worst case — up to `n^2` ones in each image, so up to `n^2 * n^2` cell pairs, each an O(1) hash bump. - Space O(n^2) — the coordinate lists plus the shift-count map, both bounded by the number of `1`-cells. ### Code (C++) ```cpp class Solution { public: int largestOverlap(vector>& img1, vector>& img2) { int n = img1.size(); vector> a, b; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (img1[i][j]) a.emplace_back(i, j); if (img2[i][j]) b.emplace_back(i, j); } unordered_map cnt; int best = 0; for (auto& p : a) for (auto& q : b) { long long dr = q.first - p.first; long long dc = q.second - p.second; long long key = dr * 100LL + dc; best = max(best, ++cnt[key]); } return best; } }; ``` ### One note The one thing worth guarding is the hash key. I flatten `(dr, dc)` into a single `long long` with `dr * 100 + dc`, and that only works because `dc` stays in `[-29, 29]` — well under the `100` multiplier, so no two distinct shifts collide. If you ever reused this pattern on a wider grid you'd have to bump the multiplier past the coordinate range, or a shift like `(1, -50)` would silently alias `(0, 50)`. Encoding a 2D key as one integer is a clean speedup over a `pair`-keyed map, but the base has to strictly exceed the span of the low component — that's the invariant to keep.