LeetCode 221. Maximal Square (javascript solution)
codingpineapple
Posted on April 25, 2021
Description:
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.
Solution:
Time Complexity : O(n^2)
Space Complexity: O(n^2)
var maximalSquare = function(matrix) {
const rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
// Create dp array
const dp = Array(rows + 1).fill(0).map(() => Array(cols + 1).fill(0));
// Keep trac of the max square length
let maxsqlen = 0;
for (let i = 1; i <= rows; i++) {
for (let j = 1; j <= cols; j++) {
// Only check cells that have a 1 in the original array
if (matrix[i-1][j-1] == '1'){
// Check if the current cell is part of a square
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
maxsqlen = Math.max(maxsqlen, dp[i][j]);
}
}
}
// Return the area of the square
return maxsqlen * maxsqlen;
};
π πͺ π
π©
codingpineapple
Posted on April 25, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
sorting Recap the highlight of the sorting algorithms using JavaScript for beginners
October 5, 2024
datastructures DSA with JS: Understanding Custom Array Data Structure in JavaScript - A Step-by-Step Guide
September 29, 2024