Maximal Square

Problem Statement

Solution 1: Maximal square using dynamic programming

function maximalSquareUsingDynamicProgramming(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    let maxSide = 0;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; 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;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareUsingDynamicProgramming(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareUsingDynamicProgramming(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareUsingDynamicProgramming(array3);  //output: 0 

Solution 2: Maximal sqaure using optimized space

function maximalSquareOptimizedSpace(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = Array(n).fill(0);
    let maxSide = 0;
    let prev = 0;

    for (let i = 0; i < m; i++) {
        let temp = 0;
        for (let j = 0; j < n; j++) {
            temp = dp[j];
            if (matrix[i][j] === '1') {
                dp[j] = Math.min(prev, Math.min(dp[j], (j > 0 ? dp[j - 1] : 0))) + 1;
                maxSide = Math.max(maxSide, dp[j]);
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareOptimizedSpace(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareOptimizedSpace(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareOptimizedSpace(array3);  //output: 0 

Solution 3: Brute force search

function maximalSquareBruteForceSearch(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    let maxSide = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                let sideLength = 1;
                while (i + sideLength < m && j + sideLength < n) {
                    let allOnes = true;
                    for (let x = i; x <= i + sideLength; x++) {
                        if (matrix[x][j + sideLength] === '0') {
                            allOnes = false;
                            break;
                        }
                    }
                    for (let y = j; y <= j + sideLength; y++) {
                        if (matrix[i + sideLength][y] === '0') {
                            allOnes = false;
                            break;
                        }
                    }
                    if (allOnes) {
                        sideLength++;
                    } else {
                        break;
                    }
                }
                maxSide = Math.max(maxSide, sideLength);
            }
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareBruteForceSearch(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareBruteForceSearch(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareBruteForceSearch(array3);  //output: 0 

Solution 4: Maximal square using prefix sum

function maximalSquareUsingPrefixSum(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    // Create a prefix sum matrix
    const prefixSum = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    let maxSide = 0;

    // Compute prefix sums
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            prefixSum[i][j] = parseInt(matrix[i - 1][j - 1]) 
                + prefixSum[i - 1][j] 
                + prefixSum[i][j - 1] 
                - prefixSum[i - 1][j - 1];
        }
    }

    // Function to get sum of submatrix
    function getSum(x1, y1, x2, y2) {
        return prefixSum[x2 + 1][y2 + 1]
            - prefixSum[x1][y2 + 1]
            - prefixSum[x2 + 1][y1]
            + prefixSum[x1][y1];
    }

    // Check for each possible square size
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let sideLength = 1;
            while (i + sideLength <= m && j + sideLength <= n) {
                if (getSum(i, j, i + sideLength - 1, j + sideLength - 1) === sideLength * sideLength) {
                    sideLength++;
                } else {
                    break;
                }
            }
            maxSide = Math.max(maxSide, sideLength - 1);
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareUsingPrefixSum(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareUsingPrefixSum(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareUsingPrefixSum(array3);  //output: 0 

Solution 5: Stack Based solution for maximal square

function maximalSquareStackBased(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const heights = Array(n).fill(0);
    let maxSide = 0;

    for (let i = 0; i < m; i++) {
        const stack = [];
        for (let j = 0; j < n; j++) {
            heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
            while (stack.length && heights[j] < heights[stack[stack.length - 1]]) {
                const h = heights[stack.pop()];
                const w = stack.length ? j - stack[stack.length - 1] - 1 : j;
                maxSide = Math.max(maxSide, Math.min(h, w));
            }
            stack.push(j);
        }
        while (stack.length) {
            const h = heights[stack.pop()];
            const w = stack.length ? n - stack[stack.length - 1] - 1 : n;
            maxSide = Math.max(maxSide, Math.min(h, w));
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareStackBased(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareStackBased(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareStackBased(array3);  //output: 0 

Solution 6: Recursive approach for maximal square

function maximalSquareRecursiveApproach(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    let maxSide = 0;

    function getMaxSquareSide(i, j) {
        if (i >= m || j >= n || matrix[i][j] === '0') return 0;
        let side = 1;
        while (i + side < m && j + side < n) {
            for (let x = j; x <= j + side; x++) {
                if (matrix[i + side][x] === '0') return side;
            }
            for (let y = i; y <= i + side; y++) {
                if (matrix[y][j + side] === '0') return side;
            }
            side++;
        }
        return side;
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                maxSide = Math.max(maxSide, getMaxSquareSide(i, j));
            }
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareRecursiveApproach(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareRecursiveApproach(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareRecursiveApproach(array3);  //output: 0 

Solution 7: Column height method

function maximalSquareColumnHeightMethod(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    let maxSide = 0;

    const dp = Array(n).fill(0);

    for (let i = 0; i < m; i++) {
        let prev = 0, temp;
        for (let j = 0; j < n; j++) {
            temp = dp[j];
            if (matrix[i][j] === '1') {
                dp[j] = Math.min(prev, Math.min(dp[j], (j > 0 ? dp[j - 1] : 0))) + 1;
                maxSide = Math.max(maxSide, dp[j]);
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareColumnHeightMethod(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareColumnHeightMethod(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareColumnHeightMethod(array3);  //output: 0 

Solution 8: Row height method

function maximalSquareRowHeightMethod(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    let maxSide = 0;

    const dp = Array(m).fill(0).map(() => Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareRowHeightMethod(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareRowHeightMethod(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareRowHeightMethod(array3);  //output: 0 

Solution 9: Using histogram

function maximalSquareUsingHistogram(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    let maxSide = 0;

    // Initialize an array to store the heights of histograms
    const heights = Array(n).fill(0);

    // Helper function to find the largest square in a histogram
    function largestSquareInHistogram(heights) {
        const stack = [];
        let maxSide = 0;
        for (let i = 0; i <= heights.length; i++) {
            const h = i === heights.length ? 0 : heights[i];
            while (stack.length && h < heights[stack[stack.length - 1]]) {
                const height = heights[stack.pop()];
                const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
                maxSide = Math.max(maxSide, Math.min(height, width));
            }
            stack.push(i);
        }
        return maxSide;
    }

    // Iterate over each row in the matrix
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Update the height of histogram bar
            heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
        }
        // Calculate the largest square that can be formed in the histogram
        maxSide = Math.max(maxSide, largestSquareInHistogram(heights));
    }

    return maxSide * maxSide;
} 

const array1 = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
];
maximalSquareUsingHistogram(array1);  //output: 4 

const array2 = [["0","1"],["1","0"]];
maximalSquareUsingHistogram(array2);  //output: 1 

const array3 = [["0"]];
maximalSquareUsingHistogram(array3);  //output: 0 

More Problems Solutions