1139. Largest 1-Bordered Square

MediumArrayDynamic ProgrammingMatrix
Leetcode Link

Problem Description

The problem presents us with a 2-dimensional grid made up of 0s and 1s. The task is to determine the size of the largest square subgrid where all the cells on its border are filled with 1s. The size of a subgrid is defined by the number of elements it contains. If no such subgrid exists, we are to return a size of 0. This is a classic problem for exploring the concepts of dynamic programming in a 2D grid structure.

Intuition

The solution is built upon a dynamic programming approach, where we prepare auxiliary arrays down and right to store the maximum number of consecutive 1s below each cell (including the cell itself) and to the right of each cell (including the cell itself), respectively.

The process is as follows:

  • We iterate over the grid from bottom to top and from right to left. This reverse order helps us easily calculate the consecutive 1s for the down and right arrays as we can simply add 1 to the count found in the next row or column.
  • After populating the down and right arrays, we look for the largest square subgrid with all 1s on its border. We do this by trying to find a square of size k (starting from the largest possible size and decreasing the size) where in the top left corner of this square, both the number of consecutive 1s downward and rightward from this cell is at least k.
  • We also need to ensure that the bottom-left and top-right corners of the potential subgrid have at least k consecutive 1s upwards and leftwards to ensure the border is made entirely of 1s.
  • We do this by iterating over all possible positions of the grid where a square of size k can fit. If we find such a square, we immediately return its size (which is k*k).
  • If no such square is found after checking all potential positions for all potential sizes, we return 0.

Using this approach, the algorithm efficiently identifies the largest square subgrid with all 1s on its border without checking every possible subgrid exhaustively, thus reducing the time complexity significantly compared to a naive approach.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The implementation of the solution employs dynamic programming. We create two matrices called down and right. Both matrices have the same dimensions as the original grid. Each entry in down[i][j] represents the number of consecutive 1s below (and including) grid cell (i, j), extending all the way down to the bottom of the grid or until a 0 is encountered. Similarly, right[i][j] represents the number of consecutive 1s to the right (and including) grid cell (i, j), extending all the way to the right side of the grid or until a 0 is encountered.

Here is how the implementation approach breaks down:

  1. Iterate over the grid from the bottom-right corner to the top-left corner. This iteration order is critical because it allows us to build the down and right matrices by looking at the cells that have already been processed.

  2. For each cell (i, j), we check if it contains a 1. If it does, we set down[i][j] to down[i + 1][j] + 1 and right[i][j] to right[i][j + 1] + 1. If the cell is at the last row or column, we simply set down[i][j] or right[i][j] to 1. This is because there are no cells below or to the right to continue the consecutive sequence.

  3. Once the down and right matrices are filled, we iterate over all potential squares starting from the largest possible size k and decrease the size until we either find a valid square or finish checking all sizes.

  4. We look for a square starting at cell (i, j) with size k. To verify if the square's borders consist entirely of 1s, we check four conditions:

    • down[i][j] should be greater than or equal to k.
    • right[i][j] should be greater than or equal to k.
    • right[i + k - 1][j] (bottom-left corner of the square) should be greater than or equal to k.
    • down[i][j + k - 1] (top-right corner of the square) should be greater than or equal to k.

  5. If a square satisfying these conditions is found, we immediately return the size of the square, k * k, since we are iterating from the largest to the smallest possible size, ensuring that the first valid square found is also the largest.

  6. If no valid square is found after checking all possibilities, which means no square with borders made entirely of 1s exists, we return 0.

This approach uses the dynamic programming paradigm to build solutions to subproblems (the number of consecutive 1s extending downward and rightward from each cell) and uses those solutions to solve the bigger problem (finding the largest square with 1s on its border).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's illustrate the solution approach with a small example grid:

11 1 1 1 0
21 1 1 1 1
31 1 0 1 1
41 1 1 1 1
50 1 1 1 1

Following the steps of the implementation approach:

  1. Iterate over the grid from the bottom-right corner to the top-left corner.

    We start from the bottom-right cell (4, 4) of the grid and move towards the top-left cell (0, 0), calculating the down and right values for each cell.

  2. For each cell (i, j), we check if it contains a 1.

    For instance, at cell (4, 4), it contains a 1. Since it's in the last row and last column, down[4][4] and right[4][4] will both be set to 1.

  3. Fill the down and right matrices.

    Here's what the matrices look like after being filled based on step 2:

    down matrix:

    11 3 3 1 0
21 2 2 1 1
31 1 0 1 1
41 1 1 1 1
50 1 1 1 1

    right matrix:

    14 3 2 1 0
24 3 2 2 1
33 2 0 2 1
42 1 1 1 1
51 1 1 1 1

  4. Iterate over all potential squares

    Starting with k = 4 (the largest possible square based on the smallest grid dimension), check if a square of that size can exist beginning from each cell (i, j).

    From the right and down matrices, we can see that there's no cell that has both down and right values of 4. The maximum value is 3, so we can't form a square of size 4.

    Decrease k to 3 and repeat the process. Now we have multiple cells with both down and right values of at least 3. We choose one, say cell (1, 1), and check the conditions for the square's bottom-left and top-right corners as well. Since the bottom-left (3, 1) has a down value of 1, which is less than 3, this cell does not form a valid square of size 3.

    We continue to check other potential top-left corners of squares of size 3, eventually finding that cell (0, 1) satisfies all conditions:

    • down[0][1] >= 3
    • right[0][1] >= 3
    • right[0 + 3 - 1][1] (bottom-left corner) = right[2][1] >= 3
    • down[0][1 + 3 - 1] (top-right corner) = down[0][3] >= 3

  5. Return the size of the found square

    Since we've found a valid square of size 3 whose all border cells are 1, we return the size of this square: 3 * 3 which is 9.

  6. If no valid square is found

    However, if we were unable to find a valid square of size 3, we would decrease k to 2, then to 1, and if still no valid square is found, we would return 0. In this example, we found a square, so we return 9.

Through this process, we efficiently determined the largest square subgrid with all 1s on its border without needing to inspect every possible subgrid. This dynamic programming approach reduces the time complexity and provides a methodical way to find the solution.

Solution Implementation

1class Solution:
2    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
3        # Get the dimensions of the grid
4        rows, cols = len(grid), len(grid[0])
5      
6        # Initialize dynamic programming tables to store the count
7        # of continuous '1's until the current cell from the top and from the left.
8        down = [[0] * cols for _ in range(rows)]
9        right = [[0] * cols for _ in range(rows)]
10      
11        # Fill in the tables with the count of '1's
12        for row in range(rows - 1, -1, -1):
13            for col in range(cols - 1, -1, -1):
14                if grid[row][col] == 1:
15                    # If on the bottom or right edge, count is 1, otherwise add from accumulator
16                    down[row][col] = 1 + (down[row + 1][col] if row + 1 < rows else 0)
17                    right[row][col] = 1 + (right[row][col + 1] if col + 1 < cols else 0)
18      
19        # Iterate from the largest possible square to the smallest
20        for max_side in range(min(rows, cols), 0, -1):
21            # Check every possible position for the top-left corner of the square
22            for row in range(rows - max_side + 1):
23                for col in range(cols - max_side + 1):
24                    # Check if there are enough '1's to form the sides of the square
25                    if (down[row][col] >= max_side and
26                        right[row][col] >= max_side and
27                        right[row + max_side - 1][col] >= max_side and
28                        down[row][col + max_side - 1] >= max_side):
29                        # If a square is found, return its area
30                        return max_side * max_side
31      
32        # Return 0 if no 1-bordered square is found
33        return 0
34
1class Solution {
2    public int largest1BorderedSquare(int[][] grid) {
3        int rows = grid.length; // the number of rows in the grid
4        int cols = grid[0].length; // the number of columns in the grid
5        int[][] bottom = new int[rows][cols]; // DP matrix to store consecutive 1's from current cell to bottom
6        int[][] right = new int[rows][cols]; // DP matrix to store consecutive 1's from current cell to right
7
8        // Populate the bottom and right matrix with consecutive counts of 1's
9        for (int i = rows - 1; i >= 0; --i) {
10            for (int j = cols - 1; j >= 0; --j) {
11                if (grid[i][j] == 1) { // If the cell has a 1, calculate the consecutive 1's
12                    bottom[i][j] = (i + 1 < rows) ? bottom[i + 1][j] + 1 : 1;
13                    right[i][j] = (j + 1 < cols) ? right[i][j + 1] + 1 : 1;
14                }
15            }
16        }
17
18        // Iterate through all possible square sizes from large to small
19        for (int size = Math.min(rows, cols); size > 0; --size) {
20            // Check for a square with the current size
21            for (int i = 0; i <= rows - size; ++i) {
22                for (int j = 0; j <= cols - size; ++j) {
23                    // Verify if the current position can form a square of given size
24                    if (bottom[i][j] >= size && right[i][j] >= size &&
25                        right[i + size - 1][j] >= size && bottom[i][j + size - 1] >= size) {
26                        return size * size; // Return the area of the square
27                    }
28                }
29            }
30        }
31
32        return 0; // if no 1-bordered square is found, return 0
33    }
34}
35
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    int largest1BorderedSquare(std::vector<std::vector<int>>& grid) {
8        int rows = grid.size(), cols = grid[0].size();
9
10        // Create 2D arrays to store the count of continuous 1's in the down and right directions
11        int down[rows][cols];
12        int right[rows][cols];
13        // Initialize the arrays with zeros
14        std::memset(down, 0, sizeof(down));
15        std::memset(right, 0, sizeof(right));
16
17        // Fill the down and right arrays with the consecutive 1's count
18        for (int i = rows - 1; i >= 0; --i) {
19            for (int j = cols - 1; j >= 0; --j) {
20                if (grid[i][j] == 1) {
21                    down[i][j] = (i + 1 < rows) ? down[i + 1][j] + 1 : 1;
22                    right[i][j] = (j + 1 < cols) ? right[i][j + 1] + 1 : 1;
23                }
24            }
25        }
26
27        // Loop from the maximum possible size of the square to the smallest
28        for (int maxSize = std::min(rows, cols); maxSize > 0; --maxSize) {
29            // Check each possible position for the top-left corner of the square
30            for (int i = 0; i <= rows - maxSize; ++i) {
31                for (int j = 0; j <= cols - maxSize; ++j) {
32                    // Check if both vertical and horizontal sides have at least 'maxSize' 1's
33                    if (down[i][j] >= maxSize && right[i][j] >= maxSize &&
34                        right[i + maxSize - 1][j] >= maxSize &&
35                        down[i][j + maxSize - 1] >= maxSize) {
36                        // If a valid square is found, return its area
37                        return maxSize * maxSize;
38                    }
39                }
40            }
41        }
42
43        // Return 0 if no 1-bordered square is found
44        return 0;
45    }
46};
47
1function largest1BorderedSquare(grid: number[][]): number {
2    const rows = grid.length;
3    const cols = grid[0].length;
4
5    // Create 2D arrays to store the count of continuous 1s in the downward and rightward directions
6    const down: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));
7    const right: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));
8
9    // Fill the down and right arrays with the consecutive 1s count
10    for (let i = rows - 1; i >= 0; i--) {
11        for (let j = cols - 1; j >= 0; j--) {
12            if (grid[i][j] === 1) {
13                down[i][j] = (i + 1 < rows) ? down[i + 1][j] + 1 : 1;
14                right[i][j] = (j + 1 < cols) ? right[i][j + 1] + 1 : 1;
15            }
16        }
17    }
18
19    // Check for the largest possible square by looping from the maximum possible size to the smallest
20    for (let maxSize = Math.min(rows, cols); maxSize > 0; maxSize--) {
21        for (let i = 0; i <= rows - maxSize; i++) {
22            for (let j = 0; j <= cols - maxSize; j++) {
23                // Validate if both vertical and horizontal sides have at least 'maxSize' 1s
24                if (down[i][j] >= maxSize && right[i][j] >= maxSize &&
25                    right[i + maxSize - 1][j] >= maxSize &&
26                    down[i][j + maxSize - 1] >= maxSize) {
27                    // If a valid square is found, return its area
28                    return maxSize * maxSize;
29                }
30            }
31        }
32    }
33
34    // Return 0 if no 1-bordered square is found
35    return 0;
36}
37
38// Usage
39const grid = [
40    [1, 1, 1],
41    [1, 0, 1],
42    [1, 1, 1]
43];
44const largestSquare = largest1BorderedSquare(grid);
45console.log(largestSquare);  // Outputs the area of the largest 1-bordered square
46
Not Sure What to Study? Take the 2-min Quiz

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

The given Python code is for finding the largest 1-bounded square in a 2D binary grid.

Time Complexity:

The time complexity of the code can be analyzed as follows:

  • First, we have two nested loops that iterate over the entire grid of size m * n to populate the down and right matrices. This step has a complexity of O(m * n).
  • Next, we have a triple nested loop where the outer loop decreases k from min(m, n) to 1, and the two inner loops iterate over the m and n dimensions. In the worst case where k equals min(m, n), the complexity is O(m * n * min(m, n)).

Therefore, the overall time complexity is O(m * n) + O(m * n * min(m, n)) => O(m * n * min(m, n)), which is dominated by the triple nested loop.

Space Complexity:

The space complexity can be analyzed by considering the additional space used:

  • Two auxiliary matrices down and right, each of size m * n, are created. Hence, the space required for these matrices is 2 * m * n.
  • Apart from these two matrices, only a constant amount of additional space is used for indices and temporary variables.

Thus, the overall space complexity is O(m * n) because the space used for the down and right matrices dominates the space requirement.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«