The O(n) Club: Maximal Square: When DP Plays Tetris With Your Sanity

The O(n) Club: Maximal Square—When DP Plays Tetris With Your Sanity

⚡ TL;DR

Tired of brute-forcing every square in a 2D matrix of ‘1’s? Dynamic programming is your cheat code. Check the three musketeers—top, left, and diagonal neighbors—then stack your answer. Here’s how a Java developer with trust issues and a love for coffee does it:

// Find maximal square of '1's in a binary matrix
public int maximalSquare(char[][] matrix) {
  int m = matrix.length, n = matrix[0].length, max = 0;
  int[][] dp = new int[m + 1][n + 1];
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (matrix[i-1][j-1] == '1') {
        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
        max = Math.max(max, dp[i][j]);
      }
    }
  }
  return max * max;
}

🧠 How Devs Usually Mess This Up

Pro devs and noobs alike love to:

• Write 17 nested for-loops, discover brute force is slower than cold brew, and wonder why interviews have time limits.
• Mix up rows and columns, like a chef confusing salt for sugar: disaster in every bite.
• Count the length of the biggest square and forget to square it for area. Close but no quadratic cookie.

🔍 What’s Actually Going On

Visualize the matrix as a game board where every cell asks its top, left, and top-left neighbors, “How big a square can we make if I join your squad?” The smallest answer handed down from the peanut gallery, plus one, is the biggest possible square with its bottom-right at that spot. One false move (a zero), and you’re banished to the edge of the grid, no questions asked.

So it’s basically Tetris if the only piece was a perfect square and your nemesis was a smattering of stubborn 0’s.

🛠️ PseudoCode

• Prep for laziness: All hail boundary padding! Add an extra row and column of zeros to your DP matrix:
  int[][] dp = new int[m+1][n+1];
  Now you don’t need to check boundaries every time you peek up, left, or diagonal.
• Iterate the grid (1-based):
  If matrix[i-1][j-1] == '1' then:
  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  else, dp[i][j] just sits at zero.
  Update your max after each DP cell, or the biggest square cries quietly in the corner.
• Return the area, not the side: Multiply your max by itself to make math class proud.
  return max * max;

💻 The Code

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length, n = matrix[0].length, max = 0;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i-1][j-1] == '1') {
                dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }
    return max * max;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Area vs. Length: Don’t be the gal who gives length when they want area.
• Row/Col Mix-Up: i is for rows, j for columns. Swap those and summon debugging purgatory.
• Zero in the middle: One lone zero will sabotage your square empire faster than a blue shell in Mario Kart.
• Tiny/empty matrix: If nothing’s there, the answer is zero—not an existential crisis.
• Complexity: Classic DP: O(mn) for both time and space, unless you want to get spicy and go O(n) with a rolling 1D DP array.

🧠 Interviewer Brain-Tattoo

“The biggest square’s only as strong as its weakest (zero) member. Don’t build empires on shaky foundations or you’ll be back on LeetCode tomorrow.”