LeetCode 1139: Largest 1-Bordered Square Solution

Master LeetCode problem 1139 (Largest 1-Bordered Square), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1139. Largest 1-Bordered Square

Medium

Array Dynamic Programming Matrix

Problem Explanation

Explanation

We can solve this problem by iterating through each cell in the grid and considering it as the top-left corner of a square. We then expand the square in all directions (right, down, and diagonally) to find the largest square with all 1s on its border. We keep track of the maximum square size found so far.

Algorithm

Initialize a variable maxSize to store the maximum square size found.
Iterate through each cell in the grid.
For each cell, consider it as the top-left corner of a square.
Expand the square in all directions to find the largest possible square with all 1s on its border.
Update maxSize if a larger square is found.
Return maxSize as the result.

Time Complexity

The time complexity of this algorithm is O(n^3), where n is the size of the grid.

Space Complexity

The space complexity of this algorithm is O(1) as we are not using any additional data structures.

Solution Code

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int maxSize = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    int size = 1;
                    while (i + size < rows && j + size < cols) {
                        boolean isValid = true;
                        for (int k = 0; k <= size; k++) {
                            if (grid[i + k][j] == 0 || grid[i][j + k] == 0 || grid[i + size][j + k] == 0 || grid[i + k][j + size] == 0) {
                                isValid = false;
                                break;
                            }
                        }
                        if (isValid) {
                            maxSize = Math.max(maxSize, (size + 1) * (size + 1));
                        }
                        size++;
                    }
                }
            }
        }

        return maxSize;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1139 (Largest 1-Bordered Square)?

This page provides optimized solutions for LeetCode problem 1139 (Largest 1-Bordered Square) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1139 (Largest 1-Bordered Square)?

The time complexity for LeetCode 1139 (Largest 1-Bordered Square) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1139 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1139 in Java, C++, or Python.

Back to LeetCode Solutions