13 Sept 2026•Go / Python / TypeScript•Medium

Image Overlap

Find the largest overlap between two binary images under any translation.

For every pair of one-valued cells from the two images, count how often their displacement occurs. The most frequent displacement produces the maximum overlap.

complexity

O(n⁴) time in the worst case and O(n²) auxiliary space for an n × n image.

solution files

Go image-overlap/solution.go
Python image-overlap/solution.py
TypeScript image-overlap/solution.ts

Solution files

Go•image-overlap/solution.go

package main

func largestOverlap(img1 [][]int, img2 [][]int) int {
	type point struct {
		row    int
		column int
	}

	ones := func(image [][]int) []point {
		result := make([]point, 0)
		for row, values := range image {
			for column, value := range values {
				if value == 1 {
					result = append(result, point{row: row, column: column})
				}
			}
		}
		return result
	}

	shiftCount := make(map[point]int)
	best := 0
	for _, first := range ones(img1) {
		for _, second := range ones(img2) {
			shift := point{row: second.row - first.row, column: second.column - first.column}
			shiftCount[shift]++
			if shiftCount[shift] > best {
				best = shiftCount[shift]
			}
		}
	}

	return best
}

Python•image-overlap/solution.py

class Solution:
    def largestOverlap(self, img1: list[list[int]], img2: list[list[int]]) -> int:
        ones1 = [
            (row, column)
            for row, values in enumerate(img1)
            for column, value in enumerate(values)
            if value
        ]
        ones2 = [
            (row, column)
            for row, values in enumerate(img2)
            for column, value in enumerate(values)
            if value
        ]

        shifts: dict[tuple[int, int], int] = {}
        best = class="syntax-number">0
        for row1, column1 in ones1:
            for row2, column2 in ones2:
                shift = (row2 - row1, column2 - column1)
                shifts[shift] = shifts.get(shift, class="syntax-number">0) + class="syntax-number">1
                best = max(best, shifts[shift])

        return best

TypeScript•image-overlap/solution.ts

function largestOverlap(img1: number[][], img2: number[][]): number {
  const ones = (image: number[][]): Array<readonly [number, number]> =>
    image.flatMap((row, rowIndex) =>
      row.flatMap((value, columnIndex) =>
        value === class="syntax-number">1 ? [[rowIndex, columnIndex] as const] : [],
      ),
    );

  const shifts = new Map<string, number>();
  let best = class="syntax-number">0;

  for (const [row1, column1] of ones(img1)) {
    for (const [row2, column2] of ones(img2)) {
      const key = `${row2 - row1},${column2 - column1}`;
      const count = (shifts.get(key) ?? class="syntax-number">0) + class="syntax-number">1;
      shifts.set(key, count);
      best = Math.max(best, count);
    }
  }

  return best;
}