1162. As Far from Land as Possible LeetCode Solution
In this guide, you will get 1162. As Far from Land as Possible LeetCode Solution with the best time and space complexity. The solution to As Far from Land as Possible problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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. If no land or water exists in the grid, return -1.
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|.
Example 1:
Input: grid = [[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: grid = [[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.
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1
1162. As Far from Land as Possible LeetCode Solution in C++
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = grid.size();
const int n = grid[0].size();
queue<pair<int, int>> q;
int water = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 0)
++water;
else
q.emplace(i, j);
if (water == 0 || water == m * n)
return -1;
int ans = 0;
for (int d = 0; !q.empty(); ++d)
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j] = q.front();
q.pop();
ans = d;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] > 0)
continue;
q.emplace(x, y);
grid[x][y] = 2; // Mark as visited.
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1162. As Far from Land as Possible LeetCode Solution in Java
class Solution {
public int maxDistance(int[][] grid) {
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
final int m = grid.length;
final int n = grid[0].length;
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>();
int water = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 0)
++water;
else
q.offer(new Pair<>(i, j));
if (water == 0 || water == m * n)
return -1;
int ans = 0;
for (int d = 0; !q.isEmpty(); ++d)
for (int sz = q.size(); sz > 0; --sz) {
Pair<Integer, Integer> pair = q.poll();
final int i = pair.getKey();
final int j = pair.getValue();
ans = d;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] > 0)
continue;
q.offer(new Pair<>(x, y));
grid[x][y] = 2; // Mark as visited.
}
}
return ans;
}
} // code provided by PROGIEZ
1162. As Far from Land as Possible LeetCode Solution in Python
class Solution:
def maxDistance(self, grid: list[list[int]]) -> int:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(grid)
n = len(grid[0])
q = collections.deque()
water = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
water += 1
else:
q.append((i, j))
if water == 0 or water == m * n:
return -1
ans = 0
d = 0
while q:
for _ in range(len(q)):
i, j = q.popleft()
ans = d
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
if grid[x][y] > 0:
continue
q.append((x, y))
grid[x][y] = 2 # Mark as visited.
d += 1
return ans # code by PROGIEZ
