Here are the list of BFS problems that share same algorithm and has similar solving patterns.
Problem 1: Rotting Oranges
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
class Solution {
public int orangesRotting(int[][] grid) {
if(grid ==null || grid.length==0) return 0;
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int countFresh = 0;
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(grid[i][j]==2){
queue.offer(new int[]{i,j});
}
else if(grid[i][j]==1){
countFresh++;
}
}
}
if(countFresh == 0) return 0;
int count=0;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while(!queue.isEmpty())
{
count++;
int size=queue.size();
for(int i=0;i<size;i++)
{
int[] point = queue.poll();
for(int dir[]:dirs)
{
int x=point[0]+dir[0];
int y=point[1]+dir[1];
if(x<0 || y<0 ||x>=rows || y>=cols || grid[x][y]==0 || grid[x][y]==2) continue;
grid[x][y]=2;
queue.offer(new int[]{x,y});
countFresh--;
}
}
}
return countFresh == 0? count-1 :-1;
}
}Link to the problem in Leetcode: https://leetcode.com/problems/rotting-oranges/description/
Problem 2: Surrounded Regions
You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:
Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every 'O' cell.
Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.
To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation:
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.
public class Solution {
private class Point
{
private int x;
private int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public void solve(char[][] board) {
if (board.length == 0) return;
int rowN = board.length;
int colN = board[0].length;
Queue<Point> queue = new LinkedList<Point>();
for (int r = 0; r< rowN; r++){
if (board[r][0] == 'O') {
board[r][0] = '+';
queue.add(new Point(r, 0));
}
if (board[r][colN-1] == 'O') {
board[r][colN-1] = '+';
queue.add(new Point(r, colN-1));
}
}
for (int c = 0; c< colN; c++){
if (board[0][c] == 'O') {
board[0][c] = '+';
queue.add(new Point(0, c));
}
if (board[rowN-1][c] == 'O') {
board[rowN-1][c] = '+';
queue.add(new Point(rowN-1, c));
}
}
while (!queue.isEmpty())
{
Point p = queue.poll();
int row = p.x;
int col = p.y;
if (row - 1 >= 0 && board[row-1][col] == 'O') {board[row-1][col] = '+'; queue.add(new Point(row-1, col));}
if (row + 1 < rowN && board[row+1][col] == 'O') {board[row+1][col] = '+'; queue.add(new Point(row+1, col));}
if (col - 1 >= 0 && board[row][col - 1] == 'O') {board[row][col-1] = '+'; queue.add(new Point(row, col-1));}
if (col + 1 < colN && board[row][col + 1] == 'O') {board[row][col+1] = '+'; queue.add(new Point(row, col+1));}
}
for (int i = 0; i<rowN; i++){
for (int j=0; j<colN; j++){
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '+') board[i][j] = 'O';
}
}
}
}Link to the problem in Leetcode: https://leetcode.com/problems/surrounded-regions/description/
Problem 3: Pacific Atlantic Water Flow
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below: [0,4]: [0,4] -> Pacific Ocean [0,4] -> Atlantic Ocean [1,3]: [1,3] -> [0,3] -> Pacific Ocean [1,3] -> [1,4] -> Atlantic Ocean [1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean [1,4] -> Atlantic Ocean [2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean [3,0]: [3,0] -> Pacific Ocean [3,0] -> [4,0] -> Atlantic Ocean [3,1]: [3,1] -> [3,0] -> Pacific Ocean [3,1] -> [4,1] -> Atlantic Ocean [4,0]: [4,0] -> Pacific Ocean [4,0] -> Atlantic Ocean Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
class Solution {
private static final int[][] dir = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
private int numRows;
private int numCols;
private int[][] landHeights;
public List<List<Integer>> pacificAtlantic(int[][] matrix)
{
if (matrix.length == 0 || matrix[0].length == 0) {
return new ArrayList<>();
}
numRows = matrix.length;
numCols = matrix[0].length;
landHeights = matrix;
Queue<int[]> pacific = new LinkedList<>();
Queue<int[]> atlantic = new LinkedList<>();
for (int i = 0; i < numRows; i++)
{
pacific.offer(new int[]{i, 0});
atlantic.offer(new int[]{i, numCols - 1});
}
for (int i = 0; i < numCols; i++)
{
pacific.offer(new int[]{0, i});
atlantic.offer(new int[]{numRows - 1, i});
}
boolean[][] pacificReach = bfs(pacific);
boolean[][] atlanticReach = bfs(atlantic);
List<List<Integer>> commonCells = new ArrayList<>();
for (int i = 0; i < numRows; i++)
{
for (int j = 0; j < numCols; j++)
{
if (pacificReach[i][j] && atlanticReach[i][j])
commonCells.add(List.of(i, j));
}
}
return commonCells;
}
private boolean[][] bfs(Queue<int[]> queue)
{
boolean[][] result = new boolean[numRows][numCols];
while (!queue.isEmpty())
{
int[] cell = queue.poll();
result[cell[0]][cell[1]] = true;
for (int[] d : dir)
{
int x = cell[0] + d[0];
int y = cell[1] + d[1];
if (x < 0 || x >= numRows || y < 0 || y >= numCols) continue;
if (result[x][y]) continue;
if (landHeights[x][y] < landHeights[cell[0]][cell[1]]) continue;
queue.offer(new int[]{x, y});
}
}
return result;
}
}Link to the problem in Leetcode: https://leetcode.com/problems/pacific-atlantic-water-flow/description/
Problem 4: Map of Highest Peak
You are given an integer matrix isWater of size m x n that represents a map of land and water cells.
If isWater[i][j] == 0, cell (i, j) is a land cell.
If isWater[i][j] == 1, cell (i, j) is a water cell.
You must assign each cell a height in a way that follows these rules:
The height of each cell must be non-negative.
If the cell is a water cell, its height must be 0.
Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).
Find an assignment of heights such that the maximum height in the matrix is maximized.
Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.
Example 1:
Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.Example 2:
Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.
Constraints:
m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] is 0 or 1.
There is at least one water cell.
Solution:
class Solution {
public int[] d={0,1,0,-1,0};
public int[][] highestPeak(int[][] isWater) {
int m = isWater.length;
int n = isWater[0].length;
int[][] height = new int[m][n];
Queue<int[]> q = new LinkedList<>();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(isWater[i][j]==1)
{
height[i][j]=0;
q.offer(new int[]{i,j});
}
else
height[i][j]=-1;
}
}
while(!q.isEmpty())
{
int[] cell = q.poll();
int row = cell[0],col=cell[1];
for(int k=0;k<4;k++)
{
int x=row+d[k], y=col+d[k+1];
if(x>=0 && x<m && y>=0 && y<n && height[x][y]<0)
{
height[x][y] = height[row][col]+1;
q.offer(new int[]{x,y});
}
}
}
return height;
}
}link in leetcode: https://leetcode.com/problems/map-of-highest-peak/description/
Problem 5: Max Area of Island
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
Example 1:
Input:
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.
Solution:
class Solution {
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0) return 0;
int res = 0;
int curr = 0;
for (int i = 0; i < grid.length; i++){
for (int j = 0; j <grid[0].length; j++){
if (grid[i][j] == 1) {
grid[i][j] = 0;
curr = bfs(grid, i, j);
res = Math.max(curr, res);
}
}
}
return res;
}
private int bfs(int[][] grid, int k, int l){
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{k, l});
int res = 0;
while(!q.isEmpty()){
int[] curr = q.poll();
res++;
final int[][] neigs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] neig : neigs){
int i = curr[0] + neig[0];
int j = curr[1] + neig[1];
if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
grid[i][j] = 0;
q.offer(new int[]{i, j});
}
}
}
return res;
}
}link of the problem: https://leetcode.com/problems/max-area-of-island/description/
Problem 6: Swim in Rising Water
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).
Example 1:
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.Example 2:
Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] Output: 16
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n2
Each value grid[i][j] is unique.
Solution:
class Solution {
private static final int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
public int swimInWater(int[][] grid) {
int n=grid.length;
boolean[][] visited = new boolean[n][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[2]-b[2]);
pq.add(new int[] {0,0,grid[0][0]});
visited[0][0] = true;
while(!pq.isEmpty())
{
int[] a= pq.poll();
for(int[] d:dir)
{
int x=a[0]+d[0], y=a[1]+d[1];
if(x<0 || x>=n || y<0 || y>=n)
continue;
if(!visited[x][y])
{
visited[x][y] = true;
int time = Math.max(a[2],grid[x][y]);
if(x==n-1 && y==n-1) return time;
pq.add(new int[] {x,y,time});
}
}
}
return 0;
}
}
link to the problem: https://leetcode.com/problems/swim-in-rising-water/description/
Problem 7: Last Day Where You Can Still Cross
There is a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively.
Initially on day 0, the entire matrix is land. However, each day a new cell becomes flooded with water. You are given a 1-based 2D array cells, where cells[i] = [ri, ci] represents that on the ith day, the cell on the rith row and cith column (1-based coordinates) will be covered with water (i.e., changed to 1).
You want to find the last day that it is possible to walk from the top to the bottom by only walking on land cells. You can start from any cell in the top row and end at any cell in the bottom row. You can only travel in the four cardinal directions (left, right, up, and down).
Return the last day where it is possible to walk from the top to the bottom by only walking on land cells.
Example 1:
Input: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
Output: 2
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.
Example 2:
Input: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
Output: 1
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 1.
Example 3:
Input: row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
Output: 3
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.
Constraints:
2 <= row, col <= 2 * 104
4 <= row col <= 2 104
cells.length == row * col
1 <= ri <= row
1 <= ci <= col
All the values of cells are unique.
Solution:
class Solution {
int[] DIR = new int[]{0, 1, 0, -1, 0};
public int latestDayToCross(int row, int col, int[][] cells) {
int left = 1, right = cells.length, days = 0;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (canWalk(cells, row, col, mid)) {
days = mid;
left = mid + 1;
} else right = mid - 1;
}
return days;
}
boolean canWalk(int[][] cells, int row, int col, int dayAt)
{
int[][] grid = new int[row][col];
for (int i = 0; i < dayAt; ++i) grid[cells[i][0]-1][cells[i][1]-1] = 1;
Queue<int[]> bfs = new ArrayDeque<>();
for (int c = 0; c < col; ++c)
{
if (grid[0][c] == 0) {
bfs.offer(new int[]{0, c});
grid[0][c] = 1;
}
}
while (!bfs.isEmpty()) {
int[] curr = bfs.poll();
int r = curr[0], c = curr[1];
if (r == row - 1) return true;
for (int i = 0; i < 4; ++i)
{
int x = r + DIR[i], y = c + DIR[i+1];
if (x < 0 || x == row || y < 0 || y == col || grid[x][y] == 1) continue;
grid[x][y] = 1;
bfs.offer(new int[]{x, y});
}
}
return false;
}
}Problem 8: Nearest Exit from Entrance in Maze
You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.
In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.
Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.
Example 1:
Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.Example 2:
Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.Example 3:
Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.Constraints:
maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] is either '.' or '+'.
entrance.length == 2
0 <= entrancerow < m
0 <= entrancecol < n
entrance will always be an empty cell.
Solution:
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int[][] shifts = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
maze[entrance[0]][entrance[1]] = '+';
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{entrance[0], entrance[1], 0});
while (!queue.isEmpty()) {
int[] node = queue.poll();
for(int[] shift : shifts) {
int x = node[0] + shift[0], y = node[1] + shift[1];
if (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == '.')
{
if (x == 0 || y == 0 || x == maze.length - 1 || y == maze[0].length - 1)
return node[2] + 1;
else {
maze[x][y] = '+';
queue.add(new int[]{x, y, node[2] + 1});
}
}
}
}
return -1;
}
}link to problem: https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/
Problem 9: Number of Islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'
Solution:
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int numIslands = 0;
int m = grid.length;
int n = grid[0].length;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
numIslands++;
queue.offer(new int[]{i, j});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0];
int y = curr[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != '1') {
continue;
}
grid[x][y] = '0';
for (int[] dir : directions) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {
queue.offer(new int[]{nx, ny});
}
}
}
}
}
}
return numIslands;
}
}link to leetcode problem: https://leetcode.com/problems/number-of-islands/
Problem 10: Making A Large Island
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.Example 2:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.Example 3:
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 0 or 1.
Solution:
class Solution {
static int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int rows;
private int cols;
public int largestIsland(int[][] grid) {
rows = grid.length;
cols = grid[0].length;
int[] areas = new int[rows * cols + 2];
int areaIndex = 2;
for(int r = 0; r < rows; r++){
for(int c = 0; c < cols; c++){
if(grid[r][c] != 1) continue;
//save the area of this ones island in unique index
areas[areaIndex] = getArea(grid, r, c, areaIndex);
areaIndex++;
}
}
int maxArea = 0;
//max area without toggling zero
for(int area : areas) maxArea = Math.max(area, maxArea);
//max area after toggling zero to one
for(int r = 0; r < rows; r++){
for(int c = 0; c < cols; c++){
if(grid[r][c] != 0) continue;
Set<Integer> seenIsland = new HashSet();
int area = 1;
for(int[] dir : DIRECTIONS){
int x = r + dir[0];
int y = c + dir[1];
if(isOutsideGrid(x, y)) continue;
if(seenIsland.contains(grid[x][y])) continue;
//mark as seen this island
seenIsland.add(grid[x][y]);
//add the island area of current direction
area += areas[grid[x][y]];
}
maxArea = Math.max(area, maxArea);
}
}
return maxArea;
}
private int getArea(int[][] grid, int r, int c, int areaIndex){
if(isOutsideGrid(r, c)) return 0;
if(grid[r][c] != 1) return 0;
//marked Visited and assign a unique index,
grid[r][c] = areaIndex;
int area = 1;
for(int[] dir : DIRECTIONS){
int x = r + dir[0];
int y = c + dir[1];
area += getArea(grid, x, y, areaIndex);
}
return area;
}
private boolean isOutsideGrid(int r, int c){
return r < 0 || r >= rows || c < 0 || c >= cols;
}
}link to problem: https://leetcode.com/problems/making-a-large-island/description/
Problem 11: Find All Groups of Farmland
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.Example 3:
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 0 or 1.
Solution:
class Solution {
static int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int rows;
private int cols;
public int largestIsland(int[][] grid) {
rows = grid.length;
cols = grid[0].length;
int[] areas = new int[rows * cols + 2];
int areaIndex = 2;
for(int r = 0; r < rows; r++){
for(int c = 0; c < cols; c++){
if(grid[r][c] != 1) continue;
//save the area of this ones island in unique index
areas[areaIndex] = getArea(grid, r, c, areaIndex);
areaIndex++;
}
}
int maxArea = 0;
//max area without toggling zero
for(int area : areas) maxArea = Math.max(area, maxArea);
//max area after toggling zero to one
for(int r = 0; r < rows; r++){
for(int c = 0; c < cols; c++){
if(grid[r][c] != 0) continue;
Set<Integer> seenIsland = new HashSet();
int area = 1;
for(int[] dir : DIRECTIONS){
int x = r + dir[0];
int y = c + dir[1];
if(isOutsideGrid(x, y)) continue;
if(seenIsland.contains(grid[x][y])) continue;
//mark as seen this island
seenIsland.add(grid[x][y]);
//add the island area of current direction
area += areas[grid[x][y]];
}
maxArea = Math.max(area, maxArea);
}
}
return maxArea;
}
private int getArea(int[][] grid, int r, int c, int areaIndex){
if(isOutsideGrid(r, c)) return 0;
if(grid[r][c] != 1) return 0;
//marked Visited and assign a unique index,
grid[r][c] = areaIndex;
int area = 1;
for(int[] dir : DIRECTIONS){
int x = r + dir[0];
int y = c + dir[1];
area += getArea(grid, x, y, areaIndex);
}
return area;
}
private boolean isOutsideGrid(int r, int c){
return r < 0 || r >= rows || c < 0 || c >= cols;
}
}Link to leetcode problem: https://leetcode.com/problems/making-a-large-island/
Комментарии