LeetCode Entry

1277. Count Square Submatrices with All Ones

20.08.2025 medium 2025 kotlin rust

Count square islands of 1

1277. Count Square Submatrices with All Ones medium blog post substack youtube

1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1087

Problem TLDR

Count square islands of 1 #medium #dp

Intuition

Reuse the previous row calculations:

  • look diagonal up-left
  • look up
  • count left

Approach

  • try to write without ifs
  • reuse the input (not in production or in interview)

Complexity

  • Time complexity: \(O(nm)\)

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

Code


// 21ms
    fun countSquares(m: Array<IntArray>) = with(m) {
        for (y in 1..<size) for (x in 1..<m[0].size)
            m[y][x] *= 1 + min(m[y][x-1], min(m[y-1][x-1], m[y-1][x]))
        sumOf { it.sum() }
    }



// 0ms
    pub fn count_squares(mut m: Vec<Vec<i32>>) -> i32 {
        for y in 1..m.len() { for x in 1..m[0].len() {
            m[y][x] *= 1 + m[y][x-1].min(m[y-1][x-1]).min(m[y-1][x])
        }} m.iter().flatten().sum()
    }



// 0ms
    int countSquares(vector<vector<int>>& m) {
        int r = 0;
        for (int y = 0; y < size(m); ++y) for (int x = 0; x < size(m[0]); ++x)
        r += m[y][x] *= 1 + (y&&x ? min(m[y-1][x-1], min(m[y][x-1], m[y-1][x])): 0);
        return r;
    }



// 85ms
    def countSquares(_, m: List[List[int]]):
        for y in range(len(m)):
            for x in range(len(m[0])):
                m[y][x] *= 1 + (y and x and min(m[y-1][x-1], m[y][x-1], m[y-1][x]))
        return sum(map(sum, m))