1162. As Far from Land as Possible
https://leetcode.com/problems/as-far-from-land-as-possible/
Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
If no land or water exists in the grid, return -1.
Example 1:
Input: [[1,0,1],[0,0,0],[1,0,1]] Output: 2 Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.
Example 2:
Input: [[1,0,0],[0,0,0],[0,0,0]] Output: 4 Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.
Note:
1 <= grid.length == grid[0].length <= 100grid[i][j]is0or1
----
Intuition
Shortest path => BFS, when exiting at first match
Longest path => BFS, so that we can count levels, and exit till q is Empty
Instead of starting from water 0, start with 1 land, and count levels
Because last increment to level is extra.. q becomes empty, return ans - 1 to avoid off by 1
Modify the input grid to avoid extra space
Corner case - check the initial q size 0 or M * N to return -1
---
Time - O(M * N)
Space - O(1)
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int maxDistance(int[][] grid) { | |
| if (grid == null || grid.length == 0 || grid[0].length == 0) { | |
| return 0; | |
| } | |
| Queue<int[]> q = new LinkedList<int[]>(); | |
| for (int r = 0; r < grid.length; r++) { | |
| for (int c = 0; c < grid[0].length; c++) { | |
| if (grid[r][c] == 1) { | |
| q.offer(new int[] {r, c}); | |
| } | |
| } | |
| } | |
| if (q.isEmpty() || q.size() == grid.length * grid[0].length) { | |
| return -1; | |
| } | |
| int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; | |
| int ans = 0; | |
| while (!q.isEmpty()) { | |
| int size = q.size(); | |
| for (int i = 0; i < size; i++) { | |
| int[] current = q.poll(); | |
| for (int[] d: dirs) { | |
| int nr = d[0] + current[0]; | |
| int nc = d[1] + current[1]; | |
| if (nr >= 0 && nc >= 0 && nr < grid.length && nc < grid[0].length && grid[nr][nc] == 0) { | |
| grid[nr][nc] = 1; | |
| q.offer(new int[] {nr, nc}); | |
| } | |
| } | |
| } | |
| ans++; | |
| } | |
| return ans - 1; | |
| } | |
| } |
