Leetcode Problem 1139. Largest 1-Bordered Square

1139. Largest 1-Bordered Square

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize two 2D arrays left and top of the same dimensions as the input grid to store the number of consecutive 1s to the left and above each cell, respectively.
  2. Populate the left and top arrays by iterating over the grid and updating the count of consecutive 1s.
  3. Initialize a variable maxSquare to keep track of the size of the largest square found so far.
  4. Iterate over all possible top-left corners of squares in the grid.
  5. For each top-left corner, determine the maximum possible size of the square that can be formed based on the left and top arrays.
  6. For each possible size, check if the bottom and right sides of the square also have enough 1s.
  7. If a valid square is found, update maxSquare if the found square is larger than the current maxSquare.
  8. After checking all possible squares, return maxSquare * maxSquare as the area of the largest square with 1s on its border.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...