835. Image Overlap

class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        int maxOverlap = 0;
        for (int dy = -(n-1); dy <= n-1; dy++) {
            for (int dx = -(n-1); dx <= n-1; dx++) {
                maxOverlap = Math.max(maxOverlap, countOverlap(img1, img2, dx, dy, n));
            }
        }
        return maxOverlap;
    }
    private int countOverlap(int[][] img1, int[][] img2, int dx, int dy, int n) {
        int count = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                int nr = r + dy;
                int nc = c + dx;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    if (img1[r][c] == 1 && img2[nr][nc] == 1) {
                        count++;
                    }
                }
            }
        } 
        return count;
    }
}

class Solution:
    def largestOverlap(self, img1, img2):
        n = len(img1)
        max_overlap = 0

        for dy in range(-(n - 1), n):
            for dx in range(-(n - 1), n):
                overlap = self.count_overlap(img1, img2, dx, dy, n)
                max_overlap = max(max_overlap, overlap)

        return max_overlap

    def count_overlap(self, img1, img2, dx, dy, n):
        count = 0

        for r in range(n):
            for c in range(n):
                nr = r + dy
                nc = c + dx

                if 0 <= nr < n and 0 <= nc < n:
                    if img1[r][c] == 1 and img2[nr][nc] == 1:
                        count += 1

        return count

class Solution {
    int countOverlap(vector<vector<int>>& img1,
                     vector<vector<int>>& img2,
                     int dx, int dy, int n) {

        int count = 0;

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {

                int nr = r + dy;
                int nc = c + dx;

                if (nr >= 0 && nr < n &&
                    nc >= 0 && nc < n) {

                    if (img1[r][c] == 1 &&
                        img2[nr][nc] == 1) {
                        count++;
                    }
                }
            }
        }

        return count;
    }

public:
    int largestOverlap(vector<vector<int>>& img1,
                       vector<vector<int>>& img2) {

        int n = img1.size();
        int maxOverlap = 0;

        for (int dy = -(n - 1); dy <= n - 1; dy++) {
            for (int dx = -(n - 1); dx <= n - 1; dx++) {

                maxOverlap = max(
                    maxOverlap,
                    countOverlap(img1, img2, dx, dy, n)
                );
            }
        }

        return maxOverlap;
    }
};

class Solution {
    largestOverlap(img1, img2) {
        const n = img1.length;
        let maxOverlap = 0;

        for (let dy = -(n - 1); dy <= n - 1; dy++) {
            for (let dx = -(n - 1); dx <= n - 1; dx++) {

                const overlap = this.countOverlap(
                    img1,
                    img2,
                    dx,
                    dy,
                    n
                );

                maxOverlap = Math.max(maxOverlap, overlap);
            }
        }

        return maxOverlap;
    }

    countOverlap(img1, img2, dx, dy, n) {
        let count = 0;

        for (let r = 0; r < n; r++) {
            for (let c = 0; c < n; c++) {

                const nr = r + dy;
                const nc = c + dx;

                if (
                    nr >= 0 && nr < n &&
                    nc >= 0 && nc < n
                ) {
                    if (
                        img1[r][c] === 1 &&
                        img2[nr][nc] === 1
                    ) {
                        count++;
                    }
                }
            }
        }

        return count;
    }
}