The O(n) Club: Counting Squares in Binary Matrices (Because Rectangles Are for Quitters)

The O(n) Club: Counting Squares in Binary Matrices (Because Rectangles Are for Quitters)

⚡ TL;DR

Counting all squares (not just the “big ones”) in a 0/1 grid? Brute force is for coffee-addled interns. Use DP: look left, up, and diagonal, then add their optimism to yours. Quick Java taste:

// Java DP flavor: count every square ending at (i, j)
int countSquares(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, sum = 0;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (matrix[i][j] != 0) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
                sum += dp[i][j];
            }
    return sum;
}

🧠 How Devs Usually Mess This Up

Let’s make you feel better: everyone messes this up at first. Usually by:

• Counting only “max” squares at each spot. No bonus points for the king-size — the little 1x1s are people too.
• Counting rectangles (because they just want to watch the world burn — or haven’t read the prompt).
• Ignoring zeroes. Sorry, but just one zero in your square and the party is over; don’t invite them.

🔍 What’s Actually Going On

Imagine you’re a robot janitor scrubbing a matrix, and every time you stand on a one, you want to brag about the biggest perfect square with you as its bottom right corner. But alas, your ego is set by your shakiest neighbor — top, left, or top-left. Your DP value at (i, j) is 1 (yourself) plus the smallest DP among those three amigos. Respect the weakest link, sum up everybody’s contributions, and you get all possible squares of all sizes accounted for. Even Larry in the corner, holding up a 1×1 by himself.

🛠️ PseudoCode

• Loop through each cell (i, j).
• If it’s a zero, move on. (Squares hate zeroes.)
• If you’re on the top/left edge, dp[i][j] = 1 if matrix[i][j] is 1.
• Otherwise:

  dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);

  This gives you all square sizes ending here.
• Add dp[i][j] to your running tally.

Repeat until the matrix is as clean as your code review PR (so: not very, unless you follow directions).

💻 The Code

public class Solution {
  public int countSquares(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, sum = 0;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (matrix[i][j] == 0) continue;
        if (i == 0 || j == 0) dp[i][j] = 1;
        else dp[i][j] = 1 + Math.min(
          Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]
        );
        sum += dp[i][j];
      }
    }
    return sum;
  }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge index goofs: Out-of-bounds will get you a stacktrace and a frowny face from Java.
• Summing only the largest square. Don’t — add up all dp values, not just max(dp).
• O(m*n) space isn’t free. Big data folks: in-place DP can save RAM, but don’t cry if you overwrite your input.
• One zero = zero square. Don’t try to sneak it in and hope the interviewer won’t notice—they will.

Complexity: O(mn) time, O(mn) space (unless you’re brave enough for in-place ninja moves).

🧠 Interviewer Brain-Tattoo

Counting squares isn’t about heroics: give every little 1×1 its day. Code for the underdog; let DP do the hard work. (It’s grid interviews, not grid warfare).