NUHMAN.com

🧩 Problem Statement

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

📘 Example

go

Input: matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
Output: 4

🧠 Approach

Dynamic Programming Approach:

To solve the problem, we can use a dynamic programming (DP) approach where we build a DP table that helps us store the size of the largest square ending at each cell. The idea is to iteratively build solutions for smaller subproblems and use them to solve larger problems.

Key Idea:

• For each cell matrix[i][j] that contains a 1, the size of the largest square whose bottom-right corner is at matrix[i][j] is determined by:
• The minimum value of the squares formed by its left, top, and top-left neighbors, plus 1.
• Formally:

lua

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

• If matrix[i][j] == 1, then dp[i][j] will store the side length of the largest square that ends at this position.
• If matrix[i][j] == 0, then dp[i][j] = 0 (no square can end here).
• The answer will be the square of the maximum value found in the DP table.

Steps:

1. Create a DP table dp of the same size as the matrix.
2. Traverse each cell in the matrix:

• If matrix[i][j] == 1, update the DP table based on its neighbors.
• Track the largest side length during the iteration.

1. The largest area is the square of the largest side length found.

✅ Go Implementation

go

package main

import "fmt"

func maximalSquare(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    m, n := len(matrix), len(matrix[0])
    dp := make([][]int, m)

    // Initialize dp array
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }

    maxSide := 0

    // Fill the DP table
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == '1' {
                if i == 0 || j == 0 {
                    // On the first row or first column, the largest square is 1 (if the value is 1)
                    dp[i][j] = 1
                } else {
                    // The largest square at (i, j) is the min of top, left, and top-left squares plus 1
                    dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
                }
                // Update the maximum square side found
                maxSide = max(maxSide, dp[i][j])
            }
        }
    }

    // Return the area of the largest square
    return maxSide * maxSide
}

// Helper function to find the minimum of two numbers
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// Helper function to find the maximum of two numbers
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    // Test case
    matrix := [][]byte{
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'},
    }

    fmt.Println(maximalSquare(matrix)) // Output: 4
}

📦 Example Usage

go

func main() {
    matrix := [][]byte{
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'},
    }

    fmt.Println(maximalSquare(matrix)) // Output: 4
}

⏱️ Time & Space Complexity

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. We iterate through each cell in the matrix once and compute the value for each cell in constant time.
• Space Complexity: O(m * n), for the DP table used to store the size of the largest square for each cell.

This approach is efficient and works well for matrices of different sizes. It ensures that we only traverse the matrix once while maintaining the DP table to compute the largest square area.