algoadvance

Leetcode 835. Image Overlap

Problem Statement

You are given two binary matrices A and B of size N x N, where 1 represents a pixel and 0 represents an empty space. We can translate one matrix over the other matrix and count the number of overlapping 1s. Your task is to find the largest possible overlap between translating the images A and B.

Clarifying Questions

1. Input Size: What is the range of values for N?
   • Typical constraint is (1 \leq N \leq 30).
2. Boundary Conditions: How do we handle matrices with all zeros?
   • If both matrices are all zeros, the result should be zero since there would be no overlap.

Strategy

To solve this problem, we can follow these steps:

1. Translate Matrix: Try every possible translation of matrix B over matrix A.
2. Count Overlaps: For each translation, count the number of overlapping 1s.
3. Identify Maximum Overlap: Keep track of the maximum overlap encountered.

Detailed Steps:

1. Padding: Extend A by padding with zeros on all sides to simplify overlap calculation.
2. Sliding Window: Slide B over A and for each position, count the number of overlapping 1s.
3. Maximum Overlap Calculation: Maintain a variable to store the maximum count of overlaps encountered during the sliding process.

Code

Here is the implementation in C++:

#include <vector>
#include <algorithm>
using namespace std;

int countOverlap(const vector<vector<int>>& A, const vector<vector<int>>& B, int rowOffset, int colOffset) {
    int N = A.size();
    int overlapCount = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int iB = i + rowOffset;
            int jB = j + colOffset;
            if (iB >= 0 && iB < N && jB >= 0 && jB < N && A[i][j] == 1 && B[iB][jB] == 1) {
                overlapCount++;
            }
        }
    }
    return overlapCount;
}

int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
    int N = A.size();
    int maxOverlap = 0;

    for (int rowOffset = -N + 1; rowOffset < N; ++rowOffset) {
        for (int colOffset = -N + 1; colOffset < N; ++colOffset) {
            maxOverlap = max(maxOverlap, max(countOverlap(A, B, rowOffset, colOffset),
                                             countOverlap(B, A, rowOffset, colOffset)));
        }
    }
    
    return maxOverlap;
}

Time Complexity

• Counting Overlap: Each call to countOverlap involves iterating through all N x N elements. This takes O(N^2) time.
• Sliding Window: We slide over a range of (2N - 1) for both rows and columns resulting in ( (2N - 1)^2 = 4N^2 - 4N + 1 ), which is approximately O(N^2).

Combining both, the total time complexity is O(N^4), which is feasible given the constraint that ( N \leq 30 ).

This approach ensures that we cover all possible translations and find the maximum overlap efficiently within the given constraints.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?