Number of Islands Problem Solution in Java

The number of islands problem involves counting connected components in a 2D grid where '1' represents land and '0' represents water, requiring efficient graph traversal techniques for optimal solutions.

1. Pattern 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 contains only '1' and '0' characters, or could there be other values?
4. Should we return the count of islands or the actual islands themselves?
5. What is the expected time complexity for follow-up optimization (e.g., O(mn) or better)?

Restate the pattern or problem type in your own words: The Number of Islands problem asks us to count connected components of '1's in a 2D binary grid where '1' represents land and '0' represents water. An island is formed by connecting adjacent '1's horizontally or vertically (not diagonally). This is a classic graph traversal problem where we need to identify and count distinct connected components.

Clarify the signal words and constraint shape that point to it:

• Signal words: "islands", "connected components", "grid traversal", "adjacent cells"
• Constraint shape: 2D grid with discrete values ('0' or '1'), need to count connected regions
• The problem involves exploring a grid structure with adjacency relationships between cells

Note any assumptions you are making:

• Grid dimensions are finite and manageable (no infinite grids)
• Grid contains only '0' and '1' characters (or equivalent boolean values)
• Adjacency is defined as horizontal or vertical neighbors only (no diagonal connections)
• The grid can be modified during traversal (if needed)

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is best suited for static scenarios where the entire input grid is available upfront. The problem requires processing the complete 2D structure to identify all connected components, making it unsuitable for streaming or online processing where data arrives incrementally.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Number of islands", "connected components", "find groups"
• Grid-based input with 0s and 1s (or similar binary states)
• "Surrounded regions" or "flood fill" problems
• Connectivity constraints (4-directional adjacency)
• Input size typically up to 500x500 elements

Why this pattern fits better than the most common alternatives: This is fundamentally a connected components problem in a 2D grid, where we need to count distinct groups of connected cells. Unlike graph traversal problems that might use adjacency lists, this is a direct grid problem where:

• BFS/DFS with flood-fill approach is optimal for counting connected components
• Union-Find could work but introduces unnecessary overhead for simple counting
• Dynamic programming approaches don't naturally apply to this connectivity problem

Conditions where a variation or related pattern applies instead:

• If the grid is very sparse (mostly 0s), we might consider only processing non-zero cells
• If the problem asks for "max area" instead of count, we'd track component sizes during traversal
• For 3D grids or more complex connectivity (diagonal neighbors), we'd adjust the neighbor checking logic

The core insight that makes this pattern work: Each connected component of 1s (or whatever represents "land") forms an island. By performing a single pass through the grid and using BFS/DFS to mark all cells in each connected component as visited, we can count the total number of such components. The key insight is that once we've processed a cell in a connected component, we don't need to revisit it — this prevents double-counting and ensures linear time complexity.

3. Approach Evolution

Interview communication script:

"My first instinct is to use a brute force approach where I iterate through each cell and whenever I find a '1', I increment my island count and then mark all connected land cells as visited. But that's O(n²) time because in the worst case, I might have to process every cell multiple times. Let me think about how to optimize this.

I notice that if I use a graph traversal approach like DFS or BFS, I can visit each cell exactly once. The key insight is that when I encounter a land cell ('1') that hasn't been visited yet, it must be part of a new island. I can then traverse all connected land cells using either DFS or BFS to mark them as visited, ensuring I don't double-count islands.

If I maintain the invariant that once a cell is marked as visited, I never process it again, I can reduce this to O(n) time complexity where n is the total number of cells. The space complexity would be O(m×n) in worst case for the visited array or O(m×n) for recursion stack depth in DFS.

I think a BFS approach might be more intuitive here because I can process all cells at the current boundary level before moving to the next level, but DFS would also work and might use less space in some cases. Let me go with BFS for clarity."

Brute-force approach and why it is not ideal: The naive approach would be to iterate through every cell in the grid, and whenever we encounter a '1', we increment our island counter and then mark all connected land cells as visited. This approach is inefficient because:

• We process the same cells multiple times
• For each new island, we might traverse the entire grid again
• Time complexity becomes O(n²) in worst case where n is total cells

Improved approach and the key optimization: The key optimization is to use graph traversal (BFS or DFS) to explore connected components once we find an unvisited land cell. Once we identify a new island, we traverse all connected land cells and mark them as visited to avoid reprocessing. This ensures each cell is processed exactly once.

Final approach with step-by-step reasoning:

1. Iterate through each cell in the grid
2. When we encounter a land cell ('1') that hasn't been visited:
   • Increment island counter
   • Perform BFS/DFS to mark all connected land cells as visited
3. Continue until all cells are processed
4. Return the total count

The invariant that must hold is: once a cell is marked as visited, it will never be reprocessed, ensuring O(n) time complexity.

Important invariants that must hold:

• Each cell is processed at most once
• When we find an unvisited '1', it's guaranteed to be part of a new island
• All connected land cells are marked as visited during traversal to prevent double counting

4. Data Structure Choice

For the Number of Islands problem, I'll use a combination of data structures to achieve an optimal solution:

Primary Data Structures:

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

   • Used to represent the input matrix where '1' represents land and '0' represents water
   • Essential for maintaining the original input structure and enabling direct access to any cell
   • Time complexity: O(1) for accessing any cell
   • Space complexity: O(m×n) where m and n are grid dimensions

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

   • Used to track which cells have been visited during traversal
   • Prevents revisiting the same land cell and ensures each island is counted exactly once
   • Time complexity: O(1) for checking visited status
   • Space complexity: O(m×n) for tracking all cells

Why These Choices Work Well:

The 2D grid is essential because we need to process the input as-is and maintain spatial relationships between cells. The visited array is crucial for avoiding double-counting islands - without it, we'd traverse the same connected component multiple times.

Alternative Considerations:

• Union-Find (Disjoint Set) could work but would add unnecessary complexity for this specific problem where we just need to count connected components
• Queue/Stack for BFS/DFS traversal - while these are used in the algorithm, they're not primary data structures but rather implementation details of our traversal approach

The combination of the original grid and visited array provides clean separation between input data and processing state, making the solution both readable and efficient. The visited array is particularly important for maintaining correctness in our island counting algorithm.

Helper Structures:

• Direction arrays (int[] dx, int[] dy) - These help in implementing the 4-directional traversal (up, down, left, right) efficiently without repetitive code
• Space complexity: O(1) - only 4 elements each, negligible compared to the main data structures

These choices support clean implementation of both BFS and DFS approaches while maintaining optimal time complexity.

5. Algorithm Walkthrough

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

int[][] grid = {
    {1, 1, 0, 0, 0},
    {1, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 1, 1}
};

Step 1: Initialize islands = 0 and create a visited boolean matrix of same dimensions.

Step 2: Start iterating from grid[0][0]. Value is 1, so we found an island cell.

Step 3: Call DFS on (0,0).

• Mark (0,0) as visited
• Check neighbors: (0,1) is 1, (1,0) is 1, both unvisited → continue DFS
• From (0,1): check neighbors, mark as visited
• From (1,0): check neighbors, mark as visited
• Continue until all connected 1s are marked as visited
• This completes one island component

Step 4: Continue iteration. When we reach (2,2), value is 1 and not visited.

• Call DFS on (2,2)
• Mark (2,2) as visited
• Check neighbors: (2,3) is 0, (3,2) is 0, (1,2) is 0, (2,1) is 0
• No more connected cells → DFS completes

Step 5: Continue iteration. When we reach (3,3), value is 1 and not visited.

• Call DFS on (3,3)
• Mark (3,3) as visited
• Check neighbors: (3,4) is 1, (4,3) is out of bounds, etc.
• Continue DFS to mark (3,4) as visited

Step 6: Final count: islands = 3 (three distinct connected components)

The algorithm correctly identifies three separate islands by using DFS to traverse and mark all connected land cells as visited, ensuring each island is counted exactly once.

graph TD
    A[Start Grid] --> B{Cell (0,0) = 1?}
    B -- Yes --> C[Call DFS]
    C --> D[Mark (0,0) Visited]
    D --> E{Neighbors Unvisited?}
    E -- Yes --> F[DFS on Neighbors]
    F --> G[Mark All Connected Visited]
    G --> H[Increment Island Count]
    H --> I{All Cells Processed?}
    I -- No --> J[Continue Iteration]
    J --> K{Cell (2,2) = 1?}
    K -- Yes --> L[Call DFS]
    L --> M[Mark (2,2) Visited]
    M --> N{Neighbors Unvisited?}
    N -- No --> O[DFS Complete]
    O --> P[Increment Island Count]
    P --> Q{All Cells Processed?}
    Q -- No --> R[Continue Iteration]
    R --> S{Cell (3,3) = 1?}
    S -- Yes --> T[Call DFS]
    T --> U[Mark (3,3) Visited]
    U --> V{Neighbors Unvisited?}
    V -- Yes --> W[DFS on Neighbors]
    W --> X[Mark All Connected Visited]
    X --> Y[Increment Island Count]
    Y --> Z{All Cells Processed?}
    Z -- Yes --> AA[Return Island Count]

6. Java Solution

public class NumberOfIslands {
    public int numIslands(char[][] grid) {
        // Handle edge cases
        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 an unvisited land cell, start a DFS
                if (grid[i][j] == '1') {
                    islandCount++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return islandCount;
    }
    
    /**
     * Depth-first search to mark all connected land cells as visited
     * @param grid The grid being processed
     * @param row Current row index
     * @param col Current column index
     */
    private void dfs(char[][] grid, int row, int col) {
        // Boundary checks and validation
        if (row < 0 || row >= grid.length || 
            col < 0 || col >= grid[0].length || 
            grid[row][col] == '0') {
            return;
        }
        
        // Mark current cell as visited by setting 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. The key insight is that each time we encounter an unvisited '1', it represents a new island, and we can then mark all connected land cells as visited using DFS to avoid counting them again. The algorithm modifies the input grid in-place to mark visited cells, which saves space but means the original data is altered.

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 exactly once during the traversal. Even though we might perform multiple DFS calls from different starting points, each cell is processed at most once. The total number of operations is bounded by the size of the grid, giving us linear time complexity relative to input dimensions.

Space Complexity: O(M × N) in the worst case for the recursion stack depth when the entire grid is filled with land ('1') cells.

In the worst-case scenario where all cells are connected as one large island, the DFS recursion stack could grow to depth equal to the total number of cells in the grid. This happens when we traverse from one corner to another, causing maximum recursion depth.

The space complexity is dominated by the recursive call stack rather than any auxiliary data structures used, making it O(M × N) in the worst case. In the best case (all water or isolated land cells), space usage would be O(1) due to tail-call optimization and minimal stack depth.

This complexity is optimal for this problem since we must examine every cell at least once to determine connectivity and island count. Any algorithm that counts islands must process all cells, making O(M × N) the best possible time complexity for this problem.

The solution is optimal in both time and space because:

1. We process each cell exactly once
2. We use minimal auxiliary space (only the recursion stack)
3. The traversal is depth-first which is efficient for connected component problems
4. No additional data structures are required beyond what's necessary for the algorithm

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty grid: An empty 2D array (null or size 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 island shapes: The algorithm must correctly count islands regardless of their shape or size
• Connected components: Islands with multiple '1's connected through 4-directional adjacency must be counted as one island
• Overcounting: Care must be taken to avoid counting the same connected component multiple times

Boundary Conditions

• Grid boundaries: When checking adjacent cells, ensure indices don't go out of bounds (0 ≤ i < rows, 0 ≤ j < cols)
• Corner cases: Cells at grid corners (0,0), (0,cols-1), (rows-1,0), (rows-1,cols-1) must be handled correctly
• Edge cell handling: Cells on the edges of the grid should properly check only valid adjacent directions

Common Implementation Mistakes

• Not marking visited cells: Failing to mark visited '1' cells can lead to infinite loops in DFS or repeated counting
• Incorrect boundary checks: Off-by-one errors when checking adjacent cells can cause ArrayIndexOutOfBoundsException
• Wrong adjacency definition: Confusing 4-directional (up/down/left/right) with 8-directional (including diagonals) adjacency
• Missing grid null checks: Not handling null input grid or null rows in the 2D array
• State persistence issues: In streaming scenarios, not properly resetting state between queries

// Example of boundary check error:
// WRONG: if (i+1 < rows && grid[i+1][j] == '1') 
// BETTER: if (i+1 < rows && i+1 >= 0 && grid[i+1][j] == '1')

9. Alternative Approaches

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

1. BFS/DFS with visited array: Instead of mutating the input grid, we can maintain a separate boolean visited array of the same dimensions. This approach preserves the original input but requires additional O(m×n) space for the visited array. The time complexity remains O(m×n) as we still need to examine each cell once.

2. Union-Find (Disjoint Set): We can model this as a connected components problem using Union-Find data structure. For each land cell, we union it with its adjacent land cells. The number of islands equals the number of connected components minus the number of water cells. This approach has O(m×n) time complexity but with higher constant factors due to union-find operations and requires additional space for the Union-Find structure.

3. Flood Fill with recursion: We can implement a recursive flood-fill approach where we recursively mark all connected land cells as visited. This is essentially the same as our DFS solution but with explicit recursion instead of a stack, which might be more intuitive for some developers.

4. Iterative approach with explicit stack: Rather than using recursion, we can implement the DFS traversal iteratively using an explicit stack. This avoids potential stack overflow issues with very large grids but requires managing the stack explicitly.

The main trade-offs are:

• Space complexity: Our solution uses O(m×n) worst-case space due to the recursion stack, while the visited array approach also uses O(m×n) but is more explicit about space usage
• Input preservation: Our solution modifies the input, while alternatives preserve it at cost of additional space or complexity
• Implementation simplicity: The recursive DFS is clean and readable, while iterative approaches require more careful handling of the stack

The chosen solution is optimal in practice for most scenarios due to its clean implementation, minimal space overhead (which is acceptable for the problem constraints), and clear logic flow.

10. Test Cases

public class NumberOfIslandsTest {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem description
        char[][] grid1 = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        };
        // Expected: 1
        
        // Test case 2: Multiple 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
        
        // Test case 3: Empty grid
        char[][] grid3 = {};
        // Expected: 0
        
        // Test case 4: Single cell island
        char[][] grid4 = {{'1'}};
        // Expected: 1
        
        // Test case 5: Single cell water
        char[][] grid5 = {{'0'}};
        // Expected: 0
        
        // Test case 6: All water
        char[][] grid6 = {
            {'0','0','0'},
            {'0','0','0'},
            {'0','0','0'}
        };
        // Expected: 0
        
        // Test case 7: All land
        char[][] grid7 = {
            {'1','1','1'},
            {'1','1','1'},
            {'1','1','1'}
        };
        // Expected: 1
        
        // Test case 8: Complex island shape
        char[][] grid8 = {
            {'1','0','1','1','1'},
            {'1','0','1','0','1'},
            {'1','1','1','0','1'}
        };
        // Expected: 1
    }
}

Sample test cases include:

• Basic case with one connected island (1 island)
• Multiple disconnected islands (3 islands)
• Edge cases like empty grid, single cell (0 or 1)
• Boundary conditions with all water or all land
• Complex island shapes that require proper traversal logic

The test cases cover typical scenarios and help validate both the core algorithm correctness and edge case handling.

11. Final Summary

The core idea is to count connected components of '1's in a 2D binary grid using either DFS or BFS traversal. This solution works by identifying each unvisited land cell ('1') as the start of a new island, then recursively exploring all connected land cells to mark them as visited. The efficiency comes from avoiding redundant traversals by maintaining a visited set and processing each cell at most once. This approach is optimal for the problem as it achieves linear time complexity relative to the input size, making it suitable for large grids in production systems.