An Interest In:
Web News this Week
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
- March 26, 2024
April 25, 2021 01:35 am GMT
Original Link: https://dev.to/cod3pineapple/leetcode-221-maximal-square-javascript-solution-1243
LeetCode 221. Maximal Square(javascript solution)
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;};
Original Link: https://dev.to/cod3pineapple/leetcode-221-maximal-square-javascript-solution-1243
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To