Best Stencil Overlap

Medium

You get two stencils, first and second: square n × n grids of zeros and ones, where 1 marks a filled cell. You may shift first as a whole by any number of cells horizontally and vertically (no rotation) and lay it over second. Cells that slide past the border are lost. After the shift, count the positions filled in both stencils at once. Return the largest such count over all possible shifts.

Example 1

first=[[0, 1], [1, 1]], second=[[1, 1], [1, 0]] → 2

Shifting the first stencil one cell left and up matches only one cell; with no shift, two cells coincide: (0, 1) and (1, 0).

Example 2

first=[[1, 0, 0], [0, 0, 0], [0, 0, 0]], second=[[0, 0, 0], [0, 0, 0], [0, 0, 1]] → 1

Move the single filled cell two down and two to the right.

Example 3

first=[[1, 1], [1, 1]], second=[[0, 0], [0, 0]] → 0

Constraints

1 ≤ n ≤ 30
len(first) = len(second) = n, each row has length n
Every cell is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Matrix

Similar problems

Sudoku Board Without Clashes Medium Turn a Square Clockwise Medium Spiral Readout Medium Spiral-Numbered Square Medium Warehouse Cart Routes Medium

Input

first=[[0, 1], [1, 1]], second=[[1, 1], [1, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 78 tests on the server, hidden ones included.