1
\$\begingroup\$

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

Given a 2d grid map of '1's (land) and '0's (water), count 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:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

Code

#include <vector>

class Solution {
public:
    std::size_t numIslands(std::vector<std::vector<char>>& grid) {
        std::size_t row_length = grid.size();

        if (!row_length) {
            return 0;
        }

        std::size_t col_length = grid[0].size();
        std::size_t islands = 0;

        // Runs depth first search for every cell
        for (std::size_t row = 0; row < row_length; row++) {
            for (std::size_t col = 0; col < col_length; col++) {
                if (grid[row][col] == '1') {
                    islands++;
                    depth_first_search(grid, row, col, row_length, col_length);
                }
            }
        }

        return islands;
    }

private:
    void depth_first_search(std::vector<std::vector<char>>& grid, const std::size_t row, const std::size_t col, const std::size_t row_length, const std::size_t col_length) {
        // Checks for grid boundaries and '0' cells
        if (row < 0 || row >= row_length || col < 0 || col >= col_length || grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0';
        // Recurse in 4 directions of grid
        depth_first_search(grid, row + 1, col, row_length, col_length);
        depth_first_search(grid, row - 1, col, row_length, col_length);
        depth_first_search(grid, row, col + 1, row_length, col_length);
        depth_first_search(grid, row, col - 1, row_length, col_length);
    }
};

LeetCode's Solution (Not for review)

class Solution {
private:
  void dfs(vector<vector<char>>& grid, int r, int c) {
    int nr = grid.size();
    int nc = grid[0].size();

    grid[r][c] = '0';
    if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
    if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
  }

public:
  int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();

    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
};

Reference

On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

Offload more functionality into depth_first_search()

One improvement your solution has over LeetCode's is that you move the grid boundary check into depth_first_search(). However, you can do more, by having it return whether you are starting on an island or in the ocean:

bool depth_first_search(...) {
    // Checks for grid boundaries and '0' cells
    if (...)
        return false;

    // We are on an island, recurse
    ...

    return true;
}

Then, the loop inside numIslands() can be simplified:

for (std::size_t row = 0; row < row_length; row++)
    for (std::size_t col = 0; col < col_length; col++)
        islands += depth_first_search(grid, row, col, row_length, col_length);

Naming things

While depth_first_search() does iterate in a depth-first fashion, it is not search for anything. Rather, it is implementing a flood fill algorithm. But here we use it to remove an island. If it also performs a check to see if there is an island at the given position, I would name it check_and_remove_island(). As Emily L. mentions, a function name that reads like foo_and_bar() is usually a hint that it should be split into a foo() and bar(). If you want to go that way, I suggest you make it so you can write the following code:

if (is_island(grid, row, col)) {
    islands++;
    remove_island(grid, row, col);
}

Get rid of the size variables

I don't think it's that useful to store the sizes into separate variables, and to pass them explicitly to depth_first_search(). This information can always easily be gotten from the variable grid. This also gets rid of the check for an empty grid:

std::size_t numIslands(std::vector<std::vector<char>>& grid) {
    size_t islands{};

    for(std::size_t row = 0; row < grid.size(); row++)
        for (std::size_t col = 0; col < grid[row].size(); col++)
            islands += check_and_remove_island(grid, row, col);

    return islands;
}

You have to modify depth_first_search() to match of course.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I disagree with moving the island check into the DFS routine. Although clever and more compact, it conflates responsibilities. The method should then be called check_island_and_remove() and that's a smell to me. \$\endgroup\$
    – Emily L.
    Commented Sep 2, 2020 at 8:58
  • 1
    \$\begingroup\$ In fact the name DFS is also wrong, it's not a search as much as a flood fill implemented with depth first recursion. But I digress... \$\endgroup\$
    – Emily L.
    Commented Sep 2, 2020 at 8:59
  • 1
    \$\begingroup\$ @EmilyL. Separating responsibilities is usually a good thing, but I think that here conflating them does make the code nicer overall. But I totally agree about depth_first_search() needing a different name! \$\endgroup\$
    – G. Sliepen
    Commented Sep 2, 2020 at 9:05
  • \$\begingroup\$ Perhaps flood \$\endgroup\$
    – L. F.
    Commented Sep 2, 2020 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.