# 200. Number of Islands (Approach 1)

## Intuition

To count the number of **disconnected islands** (connected components of '1's), we treat the grid like a graph where each land cell ('1') is a node. We perform a **DFS traversal** starting from every unvisited land cell, marking all reachable land from it as visited (by flipping '1' to '0'). Every time we initiate a DFS, we count it as a **new island**.

## Complexity

| Space Complexity | Time Complexity    |
| ---------------- | ------------------ |
| $$\text{O}(N)$$  | $$\text{O}(M\*N)$$ |

## Code

```java
// Direction vectors for up, left, down, right movements
int[] deltaRow = new int[]{-1, 0, 1, 0};
int[] deltaCol = new int[]{0, -1, 0, 1};

// Depth-First Search using stack to mark all connected land
void floodFillDFS(char[][] grid, int rows, int cols, int[] start) {
    Stack<int[]> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int[] currentCell = stack.pop();

        for (int d = 0; d < 4; ++d) {
            int newRow = currentCell[0] + deltaRow[d];
            int newCol = currentCell[1] + deltaCol[d];

            // If neighbor is within bounds and is land
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') {
                stack.push(new int[]{newRow, newCol});
                grid[newRow][newCol] = '0'; // mark as visited
            }
        }
    }
}

public int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int islandCount = 0;

    // Traverse entire grid
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == '1') {
                floodFillDFS(grid, rows, cols, new int[]{i, j}); // visit full island
                islandCount++; // found a new island
            }
        }
    }

    return islandCount;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://private-26.gitbook.io/notes/coding/medium/200.-number-of-islands-approach-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.