#221 Leetcode Maximal Square Solution in C, C++, Java, JavaScript, Python, C# Leetcode

#1 Code Example with C Programming

Code - C Programming

int test_square(char **matrix, int row, int col, int k) {
    int x;
    for (x = 0; x  < = k; x ++) {
        if (matrix[row + x][col + k] == '0' ||
            matrix[row + k][col + x] == '0') return 0;
    }
    return 1;
}
int maximalSquare(char** matrix, int matrixRowSize, int matrixColSize) {
    int max = 0;
    int i, j, k;
    for (i = 0; i  <  matrixRowSize; i ++) {
        for (j = 0; j  <  matrixColSize; j ++) {
            k = 0;
            while (i + k  <  matrixRowSize &&
                   j + k < matrixColSize &&
                   test_square(matrix, i, j, k)) {
                k ++;
            }
            max = max < k ? k : max;
        }
    }
    return max * max;
}

Input

Output

#2 Code Example with C++ Programming

Code - C++ Programming

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int maxSquare = 0;
        for(int i = 0; i < matrix.size(); i++)
            for(int j = 0; j  <  matrix[0].size(); j++)
                if(matrix[i][j] != '0') maxSquare = max(maxSquare, findSquare(matrix, i, j));
        return maxSquare;
    }
    
    int findSquare(vector < vector<char>>& matrix, int r, int c>{
        int row = r - 1;
        int col = c - 1;
        while(row >= 0 && col >= 0 && matrix[r][col] == '1' && matrix[row][c] == '1'){
            int i = row;
            int j = col;
            while(i  <  r && matrix[i][col] == '1') i++;
            while(j < c && matrix[row][j] == '1') j++;
            if(i != r || j != c) break;
            row--;
            col--;
        }
        return pow(r - row, 2);
    }
};

Input

Output

#3 Code Example with Javascript Programming

Code - Javascript Programming

const maximalSquare = function(matrix) {
    const rows = matrix.length
    const cols = rows > 0 ? matrix[0].length : 0
    const dp = Array.from(new Array(rows + 1), el => new Array(cols + 1).fill(0))
    let maxLen = 0
    for(let i = 1; i  < = rows; i++) {
        for(let j = 1; j  < = cols; j++) {
            if(matrix[i - 1][j - 1] === '1') {
               dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
               maxLen = Math.max(maxLen, dp[i][j])
            }
        }
    }
    
    return maxLen * maxLen
};

Input

Output

#4 Code Example with Python Programming

Code - Python Programming

class Solution:
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        res, count = 0, 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = int(matrix[i][j])
                if matrix[i][j] != 0:
                    count = 1
                    if j>0 and int(matrix[i][j-1]) != 0: matrix[i][j] += int(matrix[i][j-1])
                    if i-1>=0 and int(matrix[i-1][j]) != 0:
                        k, curr = i-1, []
                        while k>=0 and k>=i-matrix[i][j]+1 and int(matrix[k][j]) != 0:
                            if matrix[k][j]>= count+1:
                                curr.append(matrix[k][j])
                                if min(curr)>= count+1: count += 1
                            else: break
                            k -= 1
                res = max(res, count**2)
        return res

Input

Output

#5 Code Example with C# Programming

Code - C# Programming

using System;

namespace LeetCode
{
    public class _0221_MaximalSquare
    {
        public int MaximalSquare(char[][] matrix)
        {
            var row = matrix.Length;
            if (row == 0) return 0;
            var col = matrix[0].Length;
            if (col == 0) return 0;

            var dp = new int[col + 1];
            int prev = 0, max = 0;
            for (int i = 0; i  <  row; i++)
                for (int j = 0; j  <  col; j++)
                {
                    var temp = dp[j + 1];
                    if (matrix[i][j] == '1')
                    {
                        dp[j + 1] = Math.Min(Math.Min(dp[j], prev), dp[j + 1]) + 1;
                        max = Math.Max(max, dp[j + 1]);
                    }
                    else
                        dp[j + 1] = 0;

                    prev = temp;
                }

            return max * max;
        }
    }
}

Input