LeetCode 764: Largest Plus Sign Solution

Master LeetCode problem 764 (Largest Plus Sign), 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.

764. Largest Plus Sign

Medium

Array Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We will first preprocess the grid to calculate the length of 1's in each of the four directions (up, down, left, right) from each cell. Then, we iterate through each cell in the grid and calculate the order of the largest plus sign centered at that cell. Finally, we return the maximum order found.

Preprocessing:
- For each cell in the grid, calculate the length of consecutive 1's in each direction.
- We can use four DP arrays to store this information: up, down, left, and right.
Iterating through the grid:
- For each cell, calculate the order of the largest plus sign centered at that cell by taking the minimum of lengths in all four directions.
- Keep track of the maximum order found.
Time Complexity:
- Preprocessing requires O(n^2) time.
- Iterating through the grid requires O(n^2) time.
- Overall time complexity is O(n^2).
Space Complexity:
- We use additional space to store the DP arrays, which is O(n^2) as well.

Solution Code

class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(grid[i], 1);
        }
        
        for (int[] mine : mines) {
            grid[mine[0]][mine[1]] = 0;
        }
        
        int[][] dp = new int[n][n];
        int[][] up = new int[n][n];
        int[][] down = new int[n][n];
        int[][] left = new int[n][n];
        int[][] right = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    up[i][j] = (i > 0) ? up[i-1][j] + 1 : 1;
                    left[i][j] = (j > 0) ? left[i][j-1] + 1 : 1;
                }
            }
        }
        
        int order = 0;
        
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    down[i][j] = (i < n-1) ? down[i+1][j] + 1 : 1;
                    right[i][j] = (j < n-1) ? right[i][j+1] + 1 : 1;
                    
                    dp[i][j] = Math.min(Math.min(up[i][j], down[i][j]), Math.min(left[i][j], right[i][j]));
                    order = Math.max(order, dp[i][j]);
                }
            }
        }
        
        return order;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 764 (Largest Plus Sign)?

This page provides optimized solutions for LeetCode problem 764 (Largest Plus Sign) 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 764 (Largest Plus Sign)?

The time complexity for LeetCode 764 (Largest Plus Sign) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 764 on DevExCode?

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

Back to LeetCode Solutions