Battleships in a Board Solution

Problem

Given an m × n grid where 'X' marks a battleship cell and '.' is water, count how many battleships are on the board. Each battleship occupies one or more consecutive cells in a single row or column, and no two battleships are ever adjacent — they are always separated by at least one water cell.

X . . X
. . . X
. . . X

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2
Explanation: One single-cell battleship at (0, 0) and one vertical three-cell battleship occupying column 3.

Intuition

Because battleships are strictly linear and never adjacent, every battleship has exactly one "anchor" cell — the top-left corner that has no 'X' directly above it and no 'X' directly to its left. Counting only those anchors gives the total number of battleships in a single pass without any extra memory.

Approach 1 — DFS Flood Fill

Start a DFS from each unvisited 'X' cell to mark every cell of that battleship as visited, then increment the count. This is the familiar "number of islands" strategy.

Initialize a visited boolean array the same size as the board.
Iterate over every cell in the grid.
When an unvisited 'X' is found, increment the count and start a DFS.
The DFS marks all connected 'X' cells (horizontally and vertically) as visited.
Continue until all cells are processed and return the count.

1def countBattleships(board: list[list[str]]) -> int:
2    rows, cols = len(board), len(board[0])
3    visited = [[False] * cols for _ in range(rows)]
4    count = 0
5
6    def dfs(row: int, col: int) -> None:
7        if row < 0 or row >= rows or col < 0 or col >= cols:
8            return
9        if visited[row][col] or board[row][col] != 'X':
10            return
11        visited[row][col] = True
12        dfs(row + 1, col)
13        dfs(row - 1, col)
14        dfs(row, col + 1)
15        dfs(row, col - 1)
16
17    for row in range(rows):
18        for col in range(cols):
19            if board[row][col] == 'X' and not visited[row][col]:
20                dfs(row, col)
21                count += 1
22
23    return count

Time: O(m × n) — each cell is visited at most once across all DFS calls.
Space: O(m × n) — the visited array stores a boolean for every cell.

Approach 2 — Top-Left Corner Counting (Optimal)

Because battleships are linear and never adjacent, every battleship has exactly one cell with no 'X' directly above it and no 'X' directly to its left. Counting only those anchor cells requires no extra memory.

Iterate over every cell in the grid.
Skip cells that are not 'X'.
Skip 'X' cells that have an 'X' directly above — this cell is in the middle of a vertical ship, not its top.
Skip 'X' cells that have an 'X' directly to the left — this cell is in the middle of a horizontal ship, not its left end.
Every remaining 'X' is an anchor; increment the count.

1def countBattleships(board: list[list[str]]) -> int:
2    rows, cols = len(board), len(board[0])
3    count = 0
4
5    for row in range(rows):
6        for col in range(cols):
7            if board[row][col] != 'X':
8                continue
9            # An 'X' above means we're mid-ship vertically — only the topmost cell counts
10            if row > 0 and board[row - 1][col] == 'X':
11                continue
12            # An 'X' to the left means we're mid-ship horizontally — only the leftmost cell counts
13            if col > 0 and board[row][col - 1] == 'X':
14                continue
15            count += 1
16
17    return count

Time: O(m × n) — one pass through every cell.
Space: O(1) — no extra data structures needed.

Complexity Summary

Approach	Time	Space	When to use
DFS Flood Fill	O(m × n)	O(m × n)	When the problem allows a visited array and the grid could have irregular shapes
Top-Left Corner	O(m × n)	O(1)	When O(1) space is required or you want the cleanest single-pass solution

Common Mistakes

Forgetting boundary checks before the neighbor lookup: Accessing board[row - 1][col] without first checking row > 0 throws an IndexError in Python and ArrayIndexOutOfBoundsException in Java on the top row.
Checking only one direction: Verifying that there is no 'X' above but not checking to the left correctly handles vertical ships but counts every cell of a horizontal ship as a separate anchor, doubling the count.
Modifying the board to mark visited cells: Replacing 'X' with '.' during traversal works algorithmically but violates the problem's constraint that the input board must not be modified.
Running DFS from every 'X' cell without a visited structure: Starting a fresh DFS at each 'X' without tracking already-counted cells causes each cell in a multi-cell battleship to spawn its own DFS and increment the count independently.
Assuming the anchor trick generalizes: The top-left corner approach works only because battleships are guaranteed to be strictly linear and separated by water — if ships could be L-shaped or placed adjacently, this logic would silently produce wrong answers.

Battleships in a Board — Solution