835. Image Overlap LeetCode Solution

In this guide, you will get 835. Image Overlap LeetCode Solution with the best time and space complexity. The solution to Image Overlap problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Image Overlap solution in C++
Image Overlap solution in Java
Image Overlap solution in Python
Additional Resources

835. Image Overlap LeetCode Solution image

Problem Statement of Image Overlap

You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.
We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.
Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.
Return the largest possible overlap.

Example 1:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

The number of positions that have a 1 in both images is 3 (shown in red).

Example 2:

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

Example 3:

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

Constraints:

n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j] is either 0 or 1.
img2[i][j] is either 0 or 1.

Complexity Analysis

Time Complexity: O(n^4)
Space Complexity: O(n^2)

835. Image Overlap LeetCode Solution in C++

class Solution {
 public:
  int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
    constexpr int kMagic = 100;
    const int n = img1.size();
    int ans = 0;
    vector<pair<int, int>> ones1;
    vector<pair<int, int>> ones2;
    unordered_map<int, int> offsetCount;

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        if (img1[i][j] == 1)
          ones1.emplace_back(i, j);
        if (img2[i][j] == 1)
          ones2.emplace_back(i, j);
      }

    for (const auto& [ax, ay] : ones1)
      for (const auto& [bx, by] : ones2)
        ++offsetCount[(ax - bx) * kMagic + (ay - by)];

    for (const auto& [_, count] : offsetCount)
      ans = max(ans, count);

    return ans;
  }
};
/* code provided by PROGIEZ */

835. Image Overlap LeetCode Solution in Java

class Solution {
  public int largestOverlap(int[][] img1, int[][] img2) {
    final int kMagic = 100;
    final int n = img1.length;
    int ans = 0;
    List<int[]> ones1 = new ArrayList<>();
    List<int[]> ones2 = new ArrayList<>();
    Map<Integer, Integer> offsetCount = new HashMap<>();

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        if (img1[i][j] == 1)
          ones1.add(new int[] {i, j});
        if (img2[i][j] == 1)
          ones2.add(new int[] {i, j});
      }

    for (int[] a : ones1)
      for (int[] b : ones2) {
        final int key = (a[0] - b[0]) * kMagic + a[1] - b[1];
        offsetCount.merge(key, 1, Integer::sum);
      }

    for (final int count : offsetCount.values())
      ans = Math.max(ans, count);

    return ans;
  }
}
// code provided by PROGIEZ

835. Image Overlap LeetCode Solution in Python

class Solution:
  def largestOverlap(self, img1: list[list[int]], img2: list[list[int]]) -> int:
    kMagic = 100
    ones1 = [(i, j)
             for i, row in enumerate(img1)
             for j, num in enumerate(row)
             if num == 1]
    ones2 = [(i, j)
             for i, row in enumerate(img2)
             for j, num in enumerate(row)
             if num == 1]
    offsetCount = collections.Counter()

    for ax, ay in ones1:
      for bx, by in ones2:
        offsetCount[(ax - bx) * kMagic + (ay - by)] += 1

    return max(offsetCount.values()) if offsetCount else 0
 # code by PROGIEZ