Problem Statement

You are given two images, img1 and img2, which are represented as binary matrices of size n x n. You can translate (slide) img1 in any direction (left, right, up, or down), and after sliding, you need to count how many positions have a 1 in both img1 and img2 at the same location. The goal is to find the maximum overlap between img1 and img2 for any translation of img1.

Examples

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:
Translated img1

Different Approaches

1️⃣ Brute Force Sliding

Intuition:

To maximize the overlap between img1 and img2, we can shift img1 in all possible directions within the bounds of the matrix. For each shift, we compute how many positions overlap where both matrices have 1s.

Steps:

1. For each possible translation, count the number of overlapping 1s between img1 and img2.
2. Keep track of the maximum overlap encountered during the sliding.
3. Translation involves shifting both row indices and column indices of img1 relative to img2.
4. We can slide img1 from -(n-1) to +(n-1) rows and columns, ensuring the matrices remain within bounds.

Code:

class Solution {
public:
    // Function to calculate overlap for a specific translation (dx, dy)
    int calculateOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2, int dx, int dy) {
        int n = img1.size();
        int overlap = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Check bounds and compare img1 shifted by (dx, dy) with img2
                if (i + dx >= 0 && i + dx < n && j + dy >= 0 && j + dy < n) {
                    if (img1[i + dx][j + dy] == 1 && img2[i][j] == 1) {
                        overlap++;
                    }
                }
            }
        }
        return overlap;
    }

    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size();
        int maxOverlap = 0;
        
        // Try all translations for img1 relative to img2
        for (int dx = -(n-1); dx <= n-1; dx++) {
            for (int dy = -(n-1); dy <= n-1; dy++) {
                // Calculate the overlap for the current translation (dx, dy)
                maxOverlap = max(maxOverlap, calculateOverlap(img1, img2, dx, dy));
            }
        }
        
        return maxOverlap;
    }
};

OR

class Solution {
public:
    int countOverlaps(vector<vector<int>>& A, vector<vector<int>>& B, int rowOff, int colOff) {
        int n = A.size();
        int count = 0;
        
        /*
            Uncomment these to see how the matrix is moving. For ease, take example : 
            [[0,1],[0,0]]
            [[0,0],[1,0]]
            
            cout << "\n----------------------------\n";
            cout << "Checking for rowOff = " << rowOff << ", collOff = " << colOff << endl;
        */
        
        for(int row = 0; row < n; row++) {
            for(int col = 0; col < n; col++) {
                if(row+rowOff < 0 || row+rowOff >= n || col+colOff < 0 || col+colOff >= n)
                    continue;
                
                /*
                    cout << "A[" << row << "][" << col << "] = " << A[row][col] << ", ";
                    cout  << "B[" << row+rowOff << "][" << col+colOff << "] = " << B[row+rowOff][col+colOff] << endl;
                */
                
                count += A[row][col]*B[row+rowOff][col+colOff];
            }
        }
        
        /*
            cout << "\n----------------------------\n";
        */
        
        return count;
    }
    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
        int n = A.size();
        
        int maxOverlap = 0;
        
        /*
            For ease take this example :
            [[0,1],[0,0]]
            [[0,0],[1,0]]
            
            So, we are basically having rowOffsets from (-n+1) to (n-1). Why ? Read all the comments to know
            For example : n = 2
            rowOff will have values -1, 0, 1
            colOff will have values -1, 0, 1
            
            Based on this rowOff,colOff, we will move B over A starting from "bottom left"
            1) rowOff  = -1, colOff = -1, means B is at bottom left overlapping with A[row][col] and B[row+rowOff][col+colOff]
            i.e. A[row][col] = A[1][1]
            i.e. B[row+rowOff][col+colOff] = B[0][0]
            
            2) For rowOff = -1 , we will have colOff -1, 0, 1 which means we are moving the window B towards right till we cross boundary
            
            Similarly we move ahead with rowOff  = 0, and then 1.....
        */
        
        for(int rowOff = -n+1; rowOff<n; rowOff++) {
            for(int collOff = -n+1; collOff<n; collOff++) {
                maxOverlap = max(maxOverlap, countOverlaps(A, B, rowOff, collOff));
            }
        }
        
        return maxOverlap;
    }
};

Complexity Analysis:

• Time Complexity: O(n^4)
  • The function checks for every possible translation (dx, dy) in the range [-(n-1), n-1], which gives O(n ^ 2) translations.
  • For each translation, it checks every element in both matrices, which takes O(n^2) time.
  • Total time complexity: O(n ^ 4).
• Space Complexity: O(1)
  • We only use a few additional variables that are independent of input size.