LeetCode Entry

835. Image Overlap

13.09.2026 medium 2026 kotlin rust

Best intersection after shift 2D matrix

835. Image Overlap medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1481

Problem TLDR

Best intersection after shift 2D matrix

Intuition

Brute-force. Check all the shifts.

Approach

• or group by shift vectors (dx,dy) between points

Complexity

• Time complexity: \(O(n^4)\)

• Space complexity: \(O(1)\)

Code

    fun largestOverlap(a: Array<IntArray>, b: Array<IntArray>)=
        (-29..29).run{maxOf{maxOf{u->sumOf{y->sumOf{x->
            try{b[y][x]*a[y+it][x+u]}catch(e:Exception){0}}}}}}

    pub fn largest_overlap(a: Vec<Vec<i32>>, b: Vec<Vec<i32>>) -> i32 {
        let n=a.len();*iproduct!(0..n,0..n,0..n,0..n).filter(|&(r,c,s,d)|a[r][c]*b[s][d]>0)
        .counts_by(|(r,c,s,d)|(r+29-s,c+29-d)).values().max().unwrap_or(&0)as _
    }