LeetCode-in-All

221. Maximal Square

Medium

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 1:

Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]

Output: 4

Example 2:

Input: matrix = [[“0”,”1”],[“1”,”0”]]

Output: 1

Example 3:

Input: matrix = [[“0”]]

Output: 0

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

Solution

(define/contract (maximal-square matrix)
  (-> (listof (listof char?)) exact-integer?)
  (let* ([m (length matrix)]
         [n (if (zero? m) 0 (length (first matrix)))]
         [dp (make-hash)]  ; Hash table to simulate a 2D array
         [max-size 0])

    (define (get-dp i j)
      (hash-ref dp (cons i j) 0))  ; Default to 0 if not found

    ;; Iterate over the matrix
    (for ([i (in-range m)])
      (for ([j (in-range n)])
        (when (char=? (list-ref (list-ref matrix i) j) #\1)
          (let* ([min-neighbor (min (get-dp i j) (get-dp (+ i 1) j) (get-dp i (+ j 1)))]
                 [size (+ 1 min-neighbor)])
            (hash-set! dp (cons (+ i 1) (+ j 1)) size)
            (set! max-size (max max-size size))))))

    (* max-size max-size)))  ; Return area of the largest square

This site is open source. Improve this page.