Image Overlap

MediumMatrixhashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two square binary images img1 and img2, both of size n x n, where 1 marks a filled pixel and 0 an empty one. You may slide img1 by any whole number of cells horizontally and vertically (no rotation). After the slide, the *overlap* is the number of positions where both images have a 1. Any 1 pixels that move outside the n x n frame are discarded. Return the largest overlap achievable over all possible translations (including no translation at all).

Examples

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Shifting img1 one cell right and one cell down lines up three filled pixels with img2.
Input: img1 = [[1]], img2 = [[1]]
Output: 1
No shift is needed; the single pixels coincide.
Input: img1 = [[0]], img2 = [[0]]
Output: 0
There are no filled pixels, so nothing can overlap.

Constraints

  • `n == img1.length == img1[i].length == img2.length == img2[i].length`
  • `1 <= n <= 30`
  • `img1[i][j]` and `img2[i][j]` are `0` or `1`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More hashing problems