835. Image Overlap

Problem Overview

Slide one binary image over the other by every (row, col) offset and count cells that are 1 in both.

Intuition

Slide one binary image over the other by every (row, col) offset and count cells that are 1 in both. Pack each row into a bitmask so a horizontal shift is a bit shift and an overlap count is a popcount of an AND.

Algorithm

1Encode each row of both images as a long bitmask.
2For every dr and dc in [1-n, n-1], scan overlapping rows.
3Shift the first image row by dc, mask to n bits, AND with the matching second-image row.
4Add PopCount of that AND to the overlap for this shift.
5Return the maximum overlap over all shifts.

Example Walkthrough

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]

1.Shift img1 right 1 and down 1.
2.Three positions are 1 in both images.
3.No other shift beats 3.

Output: 3

Common Pitfalls

•Bits shifted past the n-bit window must be cleared with a mask.
•Ones that leave the board do not wrap around.
•n is at most 30, so long bitmasks and O(n^3) shifts are enough.
•Empty images correctly return 0.

835.cs

// Approach: Pack each row into a bitmask. For every shift (dr, dc), AND
// overlapping rows (with horizontal shifts) and sum popcounts. Max over shifts.
// Complexity: O(n^3) time and O(n) extra space, n <= 30.
using System.Numerics;

public class Solution
{
    public int LargestOverlap(int[][] img1, int[][] img2)
    {
        int n = img1.Length;
        long[] a = new long[n];
        long[] b = new long[n];
        long mask = (1L << n) - 1;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (img1[i][j] == 1)
                    a[i] |= 1L << j;
                if (img2[i][j] == 1)
                    b[i] |= 1L << j;
            }
        }

        int ans = 0;
        for (int dr = 1 - n; dr < n; dr++)
        {
            for (int dc = 1 - n; dc < n; dc++)
            {
                int overlap = 0;
                for (int r = 0; r < n; r++)
                {
                    int r2 = r + dr;
                    if ((uint)r2 >= (uint)n)
                        continue;

                    long row = dc >= 0 ? (a[r] << dc) & mask : a[r] >> -dc;
                    overlap += BitOperations.PopCount((ulong)(row & b[r2]));
                }
                if (overlap > ans)
                    ans = overlap;
            }
        }

        return ans;
    }
}

Was this solution helpful?