Leetcode Problem 764. Largest Plus Sign

764. Largest Plus Sign

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 2D array dp of size n x n with all values set to n.
  2. Iterate over the mines array and set dp[xi][yi] to 0 for each mine location (xi, yi).
  3. For each cell (r, c) in the grid, calculate the maximum arm length in each direction:
    • Up: Iterate from r to 0 and update dp[r][c] with the minimum value encountered.
    • Down: Iterate from r to n-1 and update dp[r][c] similarly.
    • Left: Iterate from c to 0 and update dp[r][c] similarly.
    • Right: Iterate from c to n-1 and update dp[r][c] similarly.
  4. The value of dp[r][c] after these iterations will be the order of the largest plus sign centered at (r, c).
  5. Find the maximum value in the dp array, which is the final answer.
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...