Size of Islands in C++ (Time Complexity: O(m*n)) /homework

Given a 2d grid map of '1's (land) and '0's (water), find the islands and return an array containing their sizes. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Example 1:

Input:
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

Output: [9]
Explanation:  There is only one island with size 9

Example 2:

Input:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: [1, 4, 2]
Explanation There are three islands with sizes of 1, 4 and 2

Note: The islands' sizes can be returned in any order

Understanding the Problem

The core challenge of this problem is to identify and measure the size of each island in a 2D grid. An island is defined as a group of horizontally or vertically connected '1's (land). The problem is significant in various applications such as geographical mapping, image processing, and network connectivity.

Potential pitfalls include not correctly identifying all connected components or miscounting the size of an island due to improper traversal.

Approach

To solve this problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse each island and count its size. Here’s a step-by-step approach:

Naive Solution

A naive solution would involve checking each cell and starting a new traversal for each '1' found. This approach is not optimal as it may involve redundant checks and traversals.

Optimized Solution

We can optimize the solution by marking cells as visited once they are counted as part of an island. This can be done using DFS or BFS. Here, we will use DFS for simplicity.

Steps:

Initialize a visited matrix to keep track of visited cells.
Iterate through each cell in the grid.
For each '1' found, initiate a DFS to count the size of the island and mark all connected '1's as visited.
Store the size of each island in a result array.

Algorithm

Here is a detailed breakdown of the DFS algorithm:

Define a helper function to perform DFS, which will mark the current cell as visited and recursively visit all adjacent cells.
In the main function, iterate through each cell in the grid. If a cell contains '1' and is not visited, call the DFS helper function to compute the size of the island.
Store the size of each island in a result array and return it.

Code Implementation

#include <vector>
#include <iostream>

using namespace std;

// Helper function to perform DFS
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int i, int j, int &size) {
    // Check boundaries and if the cell is already visited or water
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || visited[i][j] || grid[i][j] == 0) {
        return;
    }
    
    // Mark the cell as visited
    visited[i][j] = true;
    size++;
    
    // Visit all adjacent cells (up, down, left, right)
    dfs(grid, visited, i - 1, j, size);
    dfs(grid, visited, i + 1, j, size);
    dfs(grid, visited, i, j - 1, size);
    dfs(grid, visited, i, j + 1, size);
}

vector<int> findIslandSizes(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    vector<int> islandSizes;
    
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                int size = 0;
                dfs(grid, visited, i, j, size);
                islandSizes.push_back(size);
            }
        }
    }
    
    return islandSizes;
}

int main() {
    vector<vector<int>> grid1 = {
        {1, 1, 1, 1, 0},
        {1, 1, 0, 1, 0},
        {1, 1, 0, 0, 0},
        {0, 0, 0, 0, 0}
    };
    
    vector<vector<int>> grid2 = {
        {1, 1, 0, 0, 0},
        {1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1}
    };
    
    vector<int> result1 = findIslandSizes(grid1);
    vector<int> result2 = findIslandSizes(grid2);
    
    cout << "Island sizes for grid1: ";
    for (int size : result1) {
        cout << size << " ";
    }
    cout << endl;
    
    cout << "Island sizes for grid2: ";
    for (int size : result2) {
        cout << size << " ";
    }
    cout << endl;
    
    return 0;
}

Complexity Analysis

The time complexity of the DFS approach is O(m*n), where m is the number of rows and n is the number of columns in the grid. This is because each cell is visited once. The space complexity is also O(m*n) due to the visited matrix and the recursion stack.

Edge Cases

Potential edge cases include:

All water grid: The output should be an empty array.
All land grid: The output should be an array with one element equal to the total number of cells.
Grids with multiple small islands.

Testing these edge cases ensures the robustness of the solution.

Testing

To test the solution comprehensively, consider the following test cases:

Simple grids with one or two islands.
Grids with no islands (all water).
Grids with all land.
Grids with varying sizes and shapes of islands.

Using a testing framework like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Use visual aids like diagrams to understand the problem better.
Think about edge cases and how to handle them.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving problems like finding the size of islands in a grid is crucial for developing strong problem-solving skills. It involves concepts like graph traversal and recursion, which are fundamental in computer science. Practice and exploration of similar problems can further enhance these skills.

Additional Resources

For further reading and practice, consider the following resources: