seems like first sample code already using matrix to store the visited nodes
As last line mentions, we most likely want to solve without mutating the grid argument.
Here’s my solution using a separate visited set, also tracking all the islands: https://pastebin.com/nZrm77kC
It appears this solution might be wrong, returning the wrong output on the following test case
Input:
11000
11000
00100
00011
expected output: 3
actual output: 1
All 3 official solutions have output 3.
same here im also getting output 1. instead of 3
[[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]]
any solution?
It’s correct. Just change your code from 0 to “0”. You are probably doing grid[r][c] == 0 instead of grid[r][c] == ‘0’
I changed the entire matrix into int and it ended up working
I find the recursive solution to be much cleaner. You remove an island as soon as you find it by iterating over the matrix.
def remove_island(row, col):
if grid[row][col] == 1:
grid[row][col] = 0
for neighbour in get_neighbour(row, col):
remove_island(*neighbour)
Easy to understand c++ solution. Any thoughts?
using Coordinates = pair<int, int>;
vector<Coordinates> getNeighbours(vector<vector<int>> & graph, Coordinates node, int m, int n) {
// move TOP(0, -1), RIGHT(1, 0), BOTTOM(0, 1), LEFT(-1, 0)
vector<Coordinates> dir{Coordinates(0, -1), Coordinates(1,0), Coordinates(0, 1), Coordinates(-1, 0)};
vector<Coordinates> neighbours;
for(int i = 0; i < dir.size(); i++) {
int x = node.first + dir[i].first;
int y = node.second + dir[i].second;
if(x >= 0 && y >= 0 && x < m && y < n) {
neighbours.push_back(Coordinates(x, y));
}
}
return neighbours;
}
int count_number_of_islands(std::vector<std::vector<int>> grid) {
// WRITE YOUR BRILLIANT CODE HERE
int m = grid.size();
if(m == 0)
return 0;
int n = grid[0].size();
if(n == 0)
return 0;
queue<Coordinates> q;
int count = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j]) {
q.push(Coordinates(i, j));
grid[i][j] = 0;
//cout << i << ":" << j << endl;
while(!q.empty()) {
Coordinates node = q.front();
q.pop();
vector<Coordinates> neighbours = getNeighbours(grid, node, m, n);
for(auto nextNode: neighbours) {
int _x = nextNode.first;
int _y = nextNode.second;
//cout << _x << "," << _y << endl;
if(grid[_x][_y]){
q.push(Coordinates(_x, _y));
grid[_x][_y] = 0;
}
}
}
count++;
}
}
}
return count;
}
Dfs solution, suggestions welcomed
public static int countNumberOfIslands(List<List> grid) {
int rows = grid.size();
int cols = grid.get(0).size();
int count = 0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(grid.get(i).get(j) == 1){
count++;
dfs(i,j,rows,cols,grid);
}
}
}
return count;
}
private static void dfs(int i,int j,int rows,int cols,List<List> grid){
if(i>=0 && i<rows && j>=0 && j<cols && grid.get(i).get(j) == 1){
grid.get(i).set(j,0);
dfs(i+1,j,rows,cols,grid);
dfs(i,j+1,rows,cols,grid);
dfs(i-1,j,rows,cols,grid);
dfs(i,j-1,rows,cols,grid);
}
return;
}
Wouldn’t DFS be a better solution here since with BFS space complexity is O(r*c), while with DFS space complexity is O(max(r,c))?
Structured Programming JS Solution without mutation
function countNumberOfIslands(grid) {
const numRows = grid.length;
const numCols = grid[0].length;
const visited = Array.from({ length: numRows }, () => Array(numCols).fill(false));
let count = 0;
for (let row = 0; row < numRows; row++) {
for (let col = 0; col < numCols; col++) {
if (grid[row][col] != 0 && !visited[row][col]) {
bfs(row, col, numRows, numCols, grid, visited);
count++;
}
}
}
return count;
}
function bfs(row, col, numRows, numCols, grid, visited) {
const queue = [[row, col]];
visited[row][col] = true;
while (queue.length > 0) {
const [rowIndex, colIndex] = queue.shift();
for (const neighbor of getNeighbors(rowIndex, colIndex, numRows, numCols, visited)) {
const [neighborRow, neighborCol] = neighbor;
visited[neighborRow][neighborCol] = true;
if (grid[neighborRow][neighborCol] != 0) {
queue.push(neighbor);
}
}
}
}
function getNeighbors(row, col, numRows, numCols, visited) {
const DELTA_ROW = [-1, 0, 1, 0];
const DELTA_COL = [0, 1, 0, -1];
const result = [];
for (let i = 0; i < DELTA_ROW.length; i++) {
const neighborRow = row + DELTA_ROW[i];
const neighborCol = col + DELTA_COL[i];
if (
0 <= neighborRow
&& 0 <= neighborCol
&& neighborRow < numRows
&& neighborCol < numCols
&& visited[neighborRow][neighborCol] != true
) {
result.push([neighborRow, neighborCol]);
}
}
return result;
}
The solution we type in are not stored locally anymore in the browser. Is there any issue with the website.
Solution does not work for
3
1 1 1 0 0 0
1 1 1 1 0 0 0 0 1
1 1 1 0 0 1
Welp the formatting issues. Length = 3, 3
R1: 1 1 1 0 0 0,
R2: 1 1 1 1 0 0 0 0 1,
R3: 1 1 1 0 0 1
I took a different approach… I created a hashset to keep track of every node that has yet to be visited. Then I used flood fill on islands and the ocean, removing every visited node from the hashset.
public static int countNumberOfIslands(List<List> grid) {
HashSet unvisitedSet = createUnvisitedSet(grid);
int result = 0;
while(unvisitedSet.iterator().hasNext()){
Coordinate coordinate = new Coordinate(unvisitedSet.iterator().next());
result += bfs(unvisitedSet, grid, coordinate);
}
return result;
}
public static int bfs(HashSet<String> unvisited, List<List<Integer>> grid, Coordinate startingPoint){
int containsIsland = grid.get(startingPoint.r).get(startingPoint.c);
ArrayDeque<Coordinate> queue = new ArrayDeque<>();
queue.add(startingPoint);
while(!queue.isEmpty()){
Coordinate current = queue.pop();
for(Coordinate neighbour: current.getNeighbours(grid)){
if(unvisited.contains(neighbour.serialize()) && grid.get(neighbour.r).get(neighbour.c) == containsIsland){
queue.add(neighbour);
unvisited.remove(neighbour.serialize());
}
}
unvisited.remove(current.serialize());
}
return containsIsland;
}
public static HashSet<String> createUnvisitedSet(List<List<Integer>> grid){
HashSet<String> set = new HashSet<>();
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid.get(i).size(); j++){
set.add(new Coordinate(i,j).serialize());
}
}
return set;
}
I think Test #2 is incorrect as of right now. the input is:
2
1 0 1
0 1 0
It expects 3 as an answer, but I believe 2 designates it as a 2x2 matrix. I tested this theory by changing a larger matrix into a smaller matrix in order to see the result difference.
can someone explain why for the space complexity, The number of nodes in the queue is at most twice the number of nodes in the parameter?
Why wouldn’t it be just the size of the parameter?
The solution being provided from a BFS standpoint is good but seems hard to grasp
You could probably just use DFS and return the count of islands that way. Finding neighbors is way more complicated than just saying when you encounter a “1” do a DFS across that area to verify that its an island