algoadvance

Leetcode 835. Image Overlap

Problem Statement

You are given two binary matrices img1 and img2 each of size n x n. An image overlap is the number of positions that have a 1 in both matrices. We need to translate one of the images in each of the eight possible directions (left, right, up, down) and count the maximum number of overlapping 1s for any such translation of one image over the other.

Implement a function int largestOverlap(int[][] img1, int[][] img2) that returns the maximum number of overlapping 1’s.

Clarifying Questions

  1. Is the size of the matrices always the same and a square matrix?
    • Yes, both matrices are always square matrices of the same size n x n.
  2. Can the matrices contain any values other than 0 and 1?
    • No, the matrices will only contain binary values, i.e., 0s and 1s.
  3. What are the possible values for n?
    • Generally, n could range from 1 to 30 given typical constraints for interview scenarios.

Strategy

We will use a combination of brute-force and clever shifting to solve the problem effectively:

  1. Shifting and Counting Overlaps: We will shift one matrix over the other in all possible directions and at each shift, count the number of overlaps of 1s.
  2. Using Offsets: Instead of moving the matrices, calculate the offsets and simulate the displacement using the indices.
  3. Maintain Maximum Overlap: Track the maximum overlap observed over all possible translations.

Pseudocode

  1. Initialize the maxCount to keep track of the maximum overlap.
  2. Iterate through all possible offsets (dy, dx) where dy and dx are integer values ranging from -(n-1) to n-1.
  3. For each offset, calculate the number of overlapping 1’s between img1 and the shifted img2.
  4. Update the maxCount whenever a higher overlap count is found.
  5. Return the maxCount.

Code

public class ImageOverlap {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        int maxCount = 0;

        for (int dy = -n + 1; dy < n; dy++) {
            for (int dx = -n + 1; dx < n; dx++) {
                maxCount = Math.max(maxCount, countOverlap(img1, img2, dy, dx));
            }
        }

        return maxCount;
    }

    private int countOverlap(int[][] img1, int[][] img2, int dy, int dx) {
        int n = img1.length;
        int overlap = 0;
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) {
                if (y + dy < 0 || y + dy >= n || x + dx < 0 || x + dx >= n) {
                    continue;
                }
                if (img1[y][x] == 1 && img2[y + dy][x + dx] == 1) {
                    overlap++;
                }
            }
        }
        return overlap;
    }

    public static void main(String[] args) {
        ImageOverlap io = new ImageOverlap();
        int[][] img1 = {
                {1, 1, 0},
                {0, 1, 0},
                {0, 1, 0}
        };
        int[][] img2 = {
                {0, 0, 0},
                {0, 1, 1},
                {0, 0, 1}
        };
        
        System.out.println(io.largestOverlap(img1, img2));  // Output should be 3
    }
}

Time Complexity

The time complexity of this algorithm is O(n^4) where n is the size of the matrix:

  1. Outer loops iterate over all possible offsets: (n-1) to (n-1) results in O(n^2) combinations.
  2. Inner loops count the overlap values for each offset, requiring O(n^2) operations.

Thus, the total complexity is O(n^4). While this may seem high, it is typically manageable for n up to around 30, given typical interview constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI