One can see that it has 2 for loops, which would be O(n * m), however, in the inner loop there is a breadth first search.
Because the islands are randomly generated, it seems difficult to quantify how much time this will add.
/*
https://leetcode.com/problems/number-of-islands/
*/
const grid = [
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 0],
[1, 1, 0, 0],
];
function findIslands() {
let count = 0;
// traverse each row
for(let i = 0; i < grid.length; i++) {
// traverse each column in the row
for(let j = 0; j < grid[i].length; j++) {
if(grid[i][j]) {
count++;
markIsland(i, j);
}
}
}
return count;
}
function markIsland(i, j) {
// if either out of bounds or water(0) hit, do not recurse further
if( i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] === 0 ) {
return;
}
// mark the entire island as water to avoid recursing it again
grid[i][j] = 0;
// recurse in all 4 directions
markIsland(i-1, j); // up
markIsland(i, j+1); // right
markIsland(i+1, j); // down
markIsland(i, j-1); // left
}
console.log(findIslands());
Worst-case (which this sort of complexity test is usually checking, when not otherwise specified), the number of islands is directly proportional to the length and width of the grid. For example, with a 4x4 grid, you could have 8 islands:
xoxo
oxox
xoxo
oxox
That said, the number of islands isn't really an issue for complexity here, I think, because each top-level call of markIsland will either:
markIsland (for a total of no more than length * width calls over the entire nested loop)So the overall complexity can be said to be O(n ^ 2).
It is O(N^2). The loop takes O(N^2). Then the breadth first searches count each 1 exactly one time, so in total, they take O(N^2). Thus, the total is O(N^2) + O(N^2) = O(N^2).
For problems like this, you can't use the simple time complexity calculation of just counting the loops, because the body of each loop could potentially be O(N^2), which gives you O(N^4) as a upper bound, which is too loose.