Number of Islands Problem Solution

The number of islands problem requires counting connected components of land cells in a 2D grid where '1' represents land and '0' represents water. This classic graph traversal problem can be solved efficiently using either depth-first search or breadth-first search strategies.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on the input grid dimensions (e.g., max rows/columns)?
2. Can the input grid be mutated during the solution process, or must we preserve it?
3. Are we guaranteed that the grid will only contain '1' and '0' characters, or could there be other values?
4. Should we return the count of islands or also provide the actual islands?
5. What is the expected time complexity for the solution (e.g., can we do better than O(m×n) where m and n are grid dimensions)?

Restatement in my own words: Given a 2D binary grid where '1' represents land and '0' represents water, count the number of distinct islands. An island is defined as a group of connected '1's that are adjacent either horizontally or vertically (not diagonally), and surrounded by water on all sides.

Clarification of inputs, outputs, and constraints:

• Input: A 2D char array or grid where each cell contains either '1' (land) or '0' (water)
• Output: Integer representing the total number of islands in the grid
• Constraints:
  • Grid dimensions can be up to 300×300 (based on common FAANG constraints)
  • Each cell is either '1' or '0'
  • Islands are formed by connected components of '1's in 4-directional connectivity
  • Grid can be empty or contain only water ('0's)

Assumptions I'm making:

• The grid is rectangular (same width for all rows)
• The input grid can be modified in-place (we can mark visited cells)
• We only care about counting islands, not their actual structure or coordinates
• The grid is valid (no malformed rows or out-of-bounds access)

Data shape and hidden structure: The problem represents a connected components problem in a 2D grid where each cell is a node and adjacent cells form edges. The hidden structure is that we're looking for connected components in an undirected graph, where each '1' cell is a node and edges exist between horizontally/vertically adjacent '1' cells. This suggests using either DFS or BFS traversal to find and mark all connected components.

The problem has a clear grid structure with 2D indices (row, col) and can be solved using either graph traversal techniques or Union-Find data structures. The key insight is that each connected component of '1's forms one island, and we need to count how many such components exist.

2. Pattern Recognition

Most likely patterns

The problem exhibits characteristics of Graph Traversal and Connected Components patterns.

Wording that signals the pattern

• "islands" - suggests disconnected components in a 2D grid
• "connected" - implies traversal from one cell to adjacent cells
• "count" - indicates we need to track distinct groups

Why this fits the pattern

This is fundamentally a connected components problem in a 2D grid where:

• Each land cell (1) is a node in our graph
• Adjacent land cells (up, down, left, right) form edges between nodes
• We need to count how many distinct connected components exist
• The traversal must be exhaustive - we visit all cells in one connected component before moving to the next

Core insight

The key insight is that each island represents one connected component in a 2D grid graph. We can solve this using either:

1. DFS/BFS traversal - explore each connected component once
2. Union-Find (Disjoint Set) - track connected components dynamically

The most straightforward approach is to use DFS/BFS since we're essentially counting connected components in a grid, which maps naturally to graph traversal algorithms.

The problem's structure is that of a 2D grid graph where:

• Nodes are cells with value '1'
• Edges exist between adjacent land cells (horizontally/vertically)
• We want to count the number of connected subgraphs

3. Approach Evolution

My first instinct is to use a graph traversal approach because this problem fundamentally asks us to count connected components in a 2D grid where each cell is either land (1) or water (0). If I traverse the grid and whenever I encounter a land cell that hasn't been visited yet, I can perform a DFS or BFS to mark all connected land cells as visited. This would give me the count of distinct islands.

But that's O(n²) time complexity because in the worst case, I might need to visit every cell once for each island, and that's not optimal. Let me think about how to optimize this.

I notice that if I maintain a visited array and only traverse each cell once, I can reduce it to O(n²) time but with a better constant factor. Actually, let me think more carefully - the problem is asking for the number of connected components in a grid graph, so I should think about this as a connected component problem.

The key insight is that I don't need to do multiple traversals - I can traverse once and for each unvisited land cell, increment a counter and mark all connected land cells as visited. This is essentially a single pass through the grid with O(1) extra space per cell.

Let me think about what invariant I need to maintain:

• Each land cell should only be counted once in the island count
• When I find a new land cell that hasn't been visited, it must belong to a new island
• I should mark all cells in the same connected component as visited so they don't get double-counted

The optimization comes from realizing that I can use either DFS or BFS to explore all connected land cells starting from any unvisited land cell, and once I've marked them all as visited, I don't need to process them again.

This leads me to a clean approach:

1. Iterate through each cell in the grid
2. When I find an unvisited land cell (value 1), increment island counter
3. Perform DFS/BFS to mark all connected land cells as visited
4. Continue until all cells are processed

This approach ensures each cell is processed exactly once, giving us O(m×n) time complexity where m and n are grid dimensions, and O(m×n) space for the visited array in worst case.

The key invariant that must hold is that once a land cell is marked as visited, it will never be reprocessed or counted again in any future island count operations.

4. Data Structure Choice

For the Number of Islands problem, I'll use a combination of data structures:

Primary Data Structures

1. 2D Grid (int[][] or char[][])

   • Used to represent the input matrix where '1' represents land and '0' represents water
   • This is our input storage and the primary data we're operating on
   • Time complexity: O(m×n) for traversal
   • Space complexity: O(m×n) for the input grid

2. Boolean Visited Matrix (boolean[][])

   • Used to track which cells have been visited during traversal
   • Critical for avoiding double-counting islands and preventing infinite loops in DFS/BFS
   • Time complexity: O(m×n) for initialization and operations
   • Space complexity: O(m×n) for the visited tracking

3. Queue (LinkedList or ArrayDeque)

   • Used in BFS approach to process neighboring cells level-by-level
   • Alternative to recursion stack in DFS approach
   • Time complexity: O(m×n) for all operations (amortized)
   • Space complexity: O(m×n) in worst case for queue storage

Why These Choices?

The visited matrix is essential because:

• Without it, we'd process the same land cells multiple times
• It ensures each cell is examined exactly once
• It's a standard pattern in graph traversal problems

The queue choice (vs. recursion stack) provides:

• Predictable memory usage for very large islands
• Better control over stack overflow risks in extreme cases
• Clean separation between the traversal logic and state management

Helper Structures

1. Direction Vectors (int[][])
   • Representing the four possible movements: up, down, left, right
   • Simplifies neighbor checking logic
   • Space complexity: O(1) - constant size (4 directions × 2 coordinates = 8 elements)

Trade-offs Considered

Alternative: In-place modification

• Could modify the input grid to mark visited cells (changing '1' to '0')
• Pros: Saves space O(m×n) for visited array
• Cons: Modifies input (violates principle of least surprise), not acceptable in most production code
• Not chosen for this solution as it breaks the contract of not mutating input

Alternative: Union-Find

• Could use Union-Find data structure to group connected land cells
• Pros: Elegant for dynamic connectivity problems
• Cons: Overkill for this static problem, more complex implementation, higher constant factors
• Not chosen due to unnecessary complexity for the static nature of this problem

The chosen approach uses a clean separation between input data and processing state, making it more maintainable and easier to reason about than in-place modifications.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step by step.

Consider this 4x4 grid:

[
  ['1','1','0','0'],
  ['1','1','0','0'],
  ['0','0','1','0'],
  ['0','0','0','1']
]

Step 1: Initialize islands = 0 and create a visited set to track explored cells.

Step 2: Start scanning from (0,0). Value is '1', so we found our first island.

Step 3: Trigger BFS/DFS from (0,0). The algorithm explores all connected '1's:

• Visit (0,0) → mark as visited
• Add neighbors (0,1) and (1,0) to exploration queue
• Visit (0,1) → mark as visited
• Add neighbor (1,1) to queue
• Visit (1,0) → mark as visited
• Add neighbor (1,1) to queue (already added)
• Visit (1,1) → mark as visited
• No new neighbors to add

Step 4: Increment islands = 1 and continue scanning.

Step 5: Continue scanning until we reach (2,2) where value is '1'.

• Trigger BFS/DFS from (2,2)
• Visit (2,2) → mark as visited
• Add neighbor (2,3) to queue
• Visit (2,3) → mark as visited
• No new neighbors to add

Step 6: Increment islands = 2 and continue scanning.

Step 7: Continue scanning until we reach (3,3) where value is '1'.

• Trigger BFS/DFS from (3,3)
• Visit (3,3) → mark as visited
• No neighbors to add

Step 8: Increment islands = 3 and continue scanning.

Step 9: Final result: islands = 3

The algorithm correctly identifies three separate island groups by using BFS to explore connected components and avoiding reprocessing visited cells.

Key invariants maintained:

• All visited cells are marked to prevent duplicate processing
• Only cells with value '1' are considered part of islands
• BFS ensures we process all connected land cells in one island exploration
• Grid is scanned row-by-row, column-by-column to ensure all islands are found

6. Java Solution

public class NumberOfIslands {
    public int numIslands(char[][] grid) {
        // Handle edge case of empty grid
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int rows = grid.length;
        int cols = grid[0].length();
        int islandCount = 0;
        
        // Traverse each cell in the grid
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // If we find a land cell ('1'), it's the start of a new island
                if (grid[i][j] == '1') {
                    islandCount++;
                    // Perform DFS to mark all connected land cells as visited
                    dfs(grid, i, j);
                }
            }
        }
        
        return islandCount;
    }
    
    private void dfs(char[][] grid, int row, int col) {
        // Base case: check bounds and if cell is water or already visited
        if (row < 0 || row >= grid.length || 
            col < 0 || col >= grid[0].length || 
            grid[row][col] == '0') {
            return;
        }
        
        // Mark current cell as visited by changing it to '0'
        grid[row][col] = '0';
        
        // Explore all 4 adjacent cells (up, down, left, right)
        dfs(grid, row - 1, col); // up
        dfs(grid, row + 1, col); // down
        dfs(grid, row, col - 1); // left
        dfs(grid, row, col + 1); // right
    }
}

This solution uses a depth-first search (DFS) approach to count connected components of '1' cells in a 2D grid. For each unvisited land cell, we increment our island counter and then use DFS to mark all connected land cells as visited by changing them to '0'. This prevents counting the same island multiple times. The algorithm modifies the input grid in-place to mark visited cells, which saves space but means the original data is altered. The solution handles all edge cases including empty grids, single cells, and grids with no islands.

7. Complexity Analysis

Time Complexity: O(M × N) where M is the number of rows and N is the number of columns in the grid.

Each cell in the grid is visited at most once during the traversal. The dfs method ensures that each land cell is processed exactly once, and we perform a constant amount of work for each visited cell (checking neighbors, marking as visited). Since we iterate through all cells once to find unvisited land cells, the overall time complexity is linear in terms of total grid elements.

Space Complexity: O(M × N) in the worst case for the recursion stack.

In the worst-case scenario where the entire grid is filled with land ('1'), the DFS call stack could grow to depth equal to the total number of cells in the grid. This happens when we traverse a connected component that spans the entire grid, causing recursive calls to stack up. In the best case (all water or isolated land cells), space complexity is O(1) but we must account for the worst-case scenario.

Why these bounds are correct:

• The time complexity is tight because we must examine every cell at least once to determine connected components.
• The space complexity is dominated by the maximum recursion depth, which occurs in the worst-case connected grid scenario.
• These bounds are optimal for this problem since we must process all cells to identify islands and the recursive approach requires stack space proportional to the maximum depth of connectivity.

The solution is optimal in both time and space complexity for the given constraints, as we cannot avoid visiting each cell at least once and the recursive stack depth is inherent to the problem's structure.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty grid: An empty 2D array (0×0) should return 0 islands
• Single cell grid: A single '1' returns 1 island, a single '0' returns 0 islands
• Single row/column: Grids with only one row or column need proper boundary handling

Duplicate Values and Repeated States

• Repeated '1' values: Multiple connected components of 1s should be counted as separate islands
• Island connectivity: The algorithm must properly identify connected components using 4-directional connectivity (up, down, left, right), not diagonal

Boundary Conditions

• Boundary cells: Cells at grid edges must not attempt to access invalid indices (e.g., row-1, col-1 when at row 0 or column 0)
• Array bounds: All index operations must check for valid array dimensions to prevent ArrayIndexOutOfBoundsException

Common Implementation Mistakes

• Not marking visited cells: Without marking visited cells, the same island can be counted multiple times or DFS can get stuck in infinite loops
• Incorrect neighbor checking: Forgetting to check all 4 directions (up, down, left, right) or incorrectly implementing the neighbor logic
• Modifying input grid: If the problem requires preserving input, not mutating it is crucial - though in this case, modifying the grid is acceptable since we're counting islands
• DFS stack overflow: For very large grids, recursive DFS might cause stack overflow; iterative approaches using explicit stacks can be preferred for extremely large inputs

Additional Considerations

• Memory constraints: For very large grids, the space complexity of O(m×n) for visited array or grid mutation might be a concern
• Time complexity: Ensuring that each cell is visited only once to maintain O(m×n) time complexity
• Thread safety: If used in concurrent environments, the solution should not have side effects that affect other threads

9. Alternative Approaches

There are several alternative approaches to solving the Number of Islands problem, each with different trade-offs:

1. Union-Find (Disjoint Set) Approach: This approach treats each land cell as a node and unions adjacent land cells. The time complexity is O(mn α(mn)) where α is the inverse Ackermann function, which is effectively constant. This approach is particularly useful when we need to track connected components dynamically or when the grid is very sparse. However, it requires additional space for the Union-Find data structure and has more complex implementation.

2. BFS/DFS with Grid Mutation: Instead of using a separate visited array, we could modify the input grid by marking visited land cells as water ('0'). This approach saves space but modifies the input, which might not be acceptable in some scenarios. The time complexity remains O(mn) but with a slightly higher constant factor due to the mutation operations.

3. Iterative Deepening with Flood Fill: We could implement a flood-fill approach that explores islands iteratively, but this is essentially the same as our DFS solution with a different traversal order. The complexity remains the same but might have different practical performance characteristics.

4. Bit Manipulation with Bitset: For very large grids, we could potentially use bit manipulation techniques to represent the grid more efficiently. However, this adds significant complexity and is not practical for most real-world scenarios.

The chosen solution (DFS with visited array) is preferred because it's clean, readable, and has optimal time complexity O(mn) with clear space usage. The Union-Find approach is more complex and only beneficial in specific dynamic scenarios, while the mutation approach has the disadvantage of modifying input data.

The key trade-off is between code clarity, space usage, and whether input mutation is acceptable. Our chosen solution strikes the best balance for most practical applications.

10. Test Cases

public class NumberOfIslandsTest {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Test Case 1: Basic case with multiple islands
        char[][] grid1 = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        };
        // Expected: 1
        System.out.println("Test 1: " + solution.numIslands(grid1));
        
        // Test Case 2: Multiple separate islands
        char[][] grid2 = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        // Expected: 3
        System.out.println("Test 2: " + solution.numIslands(grid2));
        
        // Test Case 3: Empty grid
        char[][] grid3 = {};
        // Expected: 0
        System.out.println("Test 3: " + solution.numIslands(grid3));
        
        // Test Case 4: Single cell island
        char[][] grid4 = {{'1'}};
        // Expected: 1
        System.out.println("Test 4: " + solution.numIslands(grid4));
        
        // Test Case 5: All water
        char[][] grid5 = {
            {'0','0','0'},
            {'0','0','0'},
            {'0','0','0'}
        };
        // Expected: 0
        System.out.println("Test 5: " + solution.numIslands(grid5));
        
        // Test Case 6: All land
        char[][] grid6 = {
            {'1','1','1'},
            {'1','1','1'},
            {'1','1','1'}
        };
        // Expected: 1
        System.out.println("Test 6: " + solution.numIslands(grid6));
        
        // Test Case 7: Complex island shape
        char[][] grid7 = {
            {'1','0','1','0','1'},
            {'0','1','0','1','0'},
            {'1','0','1','0','1'}
        };
        // Expected: 5
        System.out.println("Test 7: " + solution.numIslands(grid7));
    }
}

The test cases cover:

1. Basic connectivity: Multiple cells forming one connected island
2. Multiple islands: Separated islands with different shapes
3. Edge case - empty grid: Null or zero-sized input
4. Minimal case: Single cell grid (both land and water)
5. All water: No islands present
6. All land: Single large island
7. Alternating pattern: Complex but valid island structure

Each test case validates different aspects of the algorithm including boundary conditions, connected component detection, and edge case handling. The test cases ensure that the solution correctly identifies islands by traversing connected land cells and counts distinct groups of connected components.

11. Final Summary

The core insight is to treat the 2D grid as a graph traversal problem where each island represents a connected component of '1' cells. By using either BFS or DFS starting from any unvisited land cell, we can systematically explore and mark all cells in that connected component as visited. This approach efficiently counts islands by ensuring each cell is processed exactly once, making it optimal for the given constraints. The solution's efficiency comes from avoiding redundant work through proper state tracking and leveraging graph traversal to naturally handle the connectivity structure inherent in the problem.