Leetcode 1139: Largest 1-Bordered Square
Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has 1s on its border and 0s inside. If no such subgrid exists, return 0.
Problem
Approach
Steps
Complexity
Input: You are given a 2D grid, where each element is either 0 or 1.
Example: Input: grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Constraints:
• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 1
Output: Return the number of elements in the largest square subgrid with 1s on its border and 0s inside.
Example: Output: 9
Constraints:
• The output will be an integer representing the area of the largest square subgrid.
Goal: Find the largest square subgrid with all 1s on its border and 0s inside.
Steps:
• 1. Use dynamic programming to calculate the largest possible square that can be formed at each point.
• 2. Check the border elements of possible square subgrids to ensure they meet the condition of having 1s along the borders.
• 3. Return the area of the largest valid square found.
Goal: The problem must handle grids of size up to 100x100 efficiently.
Steps:
• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is either 0 or 1
Assumptions:
• The grid contains only 0s and 1s.
• We are looking for squares where the border consists of 1s and the inside is filled with 0s.
• Input: Input: grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
• Explanation: In this example, the largest square with all 1s on its border is the entire 3x3 grid, which has 9 elements.
• Input: Input: grid = [[1, 1, 0, 0]]
• Explanation: Here, the only valid square is the top-left corner, which is a 1x1 square with 1 on its border, giving an output of 1.
Approach: The goal is to find the largest square subgrid with 1s on its border and 0s inside, using dynamic programming to check possible squares and validate their borders.
Observations:
• Dynamic programming can be used to store the size of the largest square that can end at each point.
• We need to ensure the border of the square is composed of 1s and the inside is 0s.
• The problem is a typical dynamic programming problem where we compute the largest square at each point and then check if it satisfies the condition of having 1s on the border and 0s inside.
Steps:
• 1. Create two 2D arrays `top` and `left` to store the number of consecutive 1s from the top and left at each cell.
• 2. Loop over the grid, and for each cell, calculate how large a square can end at that cell by checking the values in `top` and `left`.
• 3. Check the border of each square for validity (all 1s on the border).
• 4. Keep track of the largest valid square and return its area.
Empty Inputs:
• An empty grid will not be given as per the constraints.
Large Inputs:
• The solution should efficiently handle grids of size 100x100.
Special Values:
• Grids where no valid square exists should return 0.
Constraints:
• The solution must be efficient enough to handle the upper limits of grid size (100x100).
int largest1BorderedSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> top(m, vector<int>(n, 0)), left(m, vector<int>(n, 0));
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] > 0) {
top[i][j] = i > 0? 1 + top[i - 1][j]: 1;
left[i][j] = j > 0? 1 + left[i][j - 1]: 1;
}
for(int l = min(m, n); l >= 1; l--) {
for(int i = 0; i < m - l + 1; i++)
for(int j = 0; j < n - l + 1; j++)
if(top[i + l - 1][j] >= l &&
top[i + l - 1][j + l - 1] >= l &&
left[i][j + l - 1] >= l &&
left[i + l - 1][j + l - 1] >= l)
return l * l;
}
return 0;
}
1 : Function Definition
int largest1BorderedSquare(vector<vector<int>>& grid) {
This defines the function `largest1BorderedSquare`, which takes a reference to a 2D vector `grid` and returns an integer representing the area of the largest square with a border of '1's.
2 : Matrix Dimensions
int m = grid.size(), n = grid[0].size();
This line initializes two variables, `m` and `n`, to store the number of rows and columns in the input `grid` respectively.
3 : DP Arrays Initialization
vector<vector<int>> top(m, vector<int>(n, 0)), left(m, vector<int>(n, 0));
This line initializes two 2D vectors, `top` and `left`, both with dimensions `m` x `n`, and fills them with zeros. These vectors will store the length of consecutive '1's up to each position in the grid (vertically for `top`, and horizontally for `left`).
4 : Loop Through Grid
for(int i = 0; i < m; i++)
This starts a loop iterating over each row of the grid.
5 : Loop Through Grid Columns
for(int j = 0; j < n; j++)
This nested loop iterates through each column of the grid in the current row.
6 : Check for '1'
if(grid[i][j] > 0) {
This `if` statement checks if the current cell in the grid contains a '1'. If so, it calculates the maximum length of consecutive '1's for this position.
7 : Top Array Update
top[i][j] = i > 0? 1 + top[i - 1][j]: 1;
If the current cell contains a '1', this line updates the `top` array at position `(i, j)` to store the length of consecutive '1's in the column, including the current cell.
8 : Left Array Update
left[i][j] = j > 0? 1 + left[i][j - 1]: 1;
This line updates the `left` array at position `(i, j)` to store the length of consecutive '1's in the row, including the current cell.
9 : Square Size Search
for(int l = min(m, n); l >= 1; l--) {
This `for` loop searches for the largest possible square that can be formed. It starts with the largest possible square size `l` (which is the minimum of the grid's dimensions) and decrements until it finds a valid square.
10 : Search Rows
for(int i = 0; i < m - l + 1; i++)
This nested loop iterates through all possible starting positions for a square of size `l` in the rows.
11 : Search Columns
for(int j = 0; j < n - l + 1; j++)
This nested loop iterates through all possible starting positions for a square of size `l` in the columns.
12 : Square Validity Check
if(top[i + l - 1][j] >= l &&
This checks if the top row of the current square of size `l` contains enough consecutive '1's (using the `top` array).
13 : Square Validity Check
top[i + l - 1][j + l - 1] >= l &&
This checks if the top-right corner of the current square contains enough consecutive '1's.
14 : Square Validity Check
left[i][j + l - 1] >= l &&
This checks if the left column of the current square contains enough consecutive '1's (using the `left` array).
15 : Square Validity Check
left[i + l - 1][j + l - 1] >= l)
This checks if the bottom-left corner of the current square contains enough consecutive '1's.
16 : Return Area of Largest Square
return l * l;
If a valid square of size `l` is found, the function returns the area of the square (i.e., `l * l`).
17 : Return 0
return 0;
If no square is found, the function returns 0, indicating that no valid square exists in the grid.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: The algorithm checks each cell in the grid and performs a constant-time operation for each, leading to a time complexity of O(m * n), where m and n are the dimensions of the grid.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The space complexity is O(m * n) due to the storage of additional 2D arrays `top` and `left`.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus