Battleships in a Board: Count Ships with One Pass

You are given an m x n board where each cell is either 'X' (part of a battleship) or '.' (empty water). Battleships are placed horizontally or vertically, never diagonally, and at least one empty cell always separates any two ships. Count how many battleships are on the board.

This is LeetCode 419: Battleships in a Board. The follow-up asks you to solve it in a single pass with O(1) extra space and without modifying the board. That constraint is what makes the problem interesting.

Why this problem matters

Battleships in a Board is a great example of how a well-chosen counting rule can eliminate the need for graph traversal entirely. The obvious approach is to treat each ship as a connected component and run DFS or BFS to find all of them. That works, but it uses O(m * n) space for the visited set and requires modifying the board or allocating extra memory.

The single-pass solution turns a graph problem into a simple scan. You do not need DFS, BFS, a visited array, or any recursion. You just need one observation: every battleship has exactly one "head" cell, the top-left cell of the ship. If you count only the heads, you count each ship exactly once.

This pattern of reducing a connected-component problem to a single linear scan shows up in other contexts too. Anytime you have non-overlapping, axis-aligned objects in a grid with guaranteed separation, you can often avoid full traversal by identifying a canonical cell for each object.

The approach

The key insight is that a cell is the "head" of a battleship if and only if:

1. The cell contains 'X'.
2. There is no 'X' directly above it (or it is in the first row).
3. There is no 'X' directly to its left (or it is in the first column).

If an 'X' cell has another 'X' above it, then this cell is part of a vertical ship whose head is further up. If it has an 'X' to its left, it is part of a horizontal ship whose head is further left. Either way, someone else already counted this ship's head.

Because battleships cannot overlap or be adjacent, every 'X' cell belongs to exactly one ship. And every ship has exactly one cell with no 'X' above and no 'X' to the left. So counting these head cells gives you the exact number of ships.

def countBattleships(board: list[list[str]]) -> int:
    rows, cols = len(board), len(board[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == ".":
                continue
            if r > 0 and board[r - 1][c] == "X":
                continue
            if c > 0 and board[r][c - 1] == "X":
                continue
            count += 1

    return count

Step-by-step walkthrough

Let's trace through the 4x4 board from the diagram. We scan every cell in row-major order (left to right, top to bottom). For each 'X', we check whether it has an 'X' above or to the left. If neither, we count it as a new ship.

The scan visits all 16 cells, but only 4 of them are 'X'. Of those 4, three pass the head check (no X above, no X to the left) and one fails (it has an X above). Final answer: 3 battleships.

Notice that we never needed to figure out the shape or extent of any ship. We never traced along a ship to find its other cells. The head-counting rule handles everything in a single pass.

Complexity analysis

Time: O(m * n). We visit every cell exactly once. Each cell does at most two comparisons (check above, check left). Total work is proportional to the board size.

Space: O(1). We use a single integer counter. No visited set, no stack, no queue. We do not modify the input board either.

Edge cases to watch for

• Empty board: if all cells are '.', the count is zero. The inner continue skips everything.
• Single cell board: [["X"]] returns 1. [["."]] returns 0. The boundary checks (r > 0, c > 0) prevent out-of-bounds access.
• All X's in one row: a single horizontal ship. Only the leftmost cell has no X to the left, so count = 1.
• All X's in one column: a single vertical ship. Only the topmost cell has no X above, so count = 1.
• Every cell is X in a 1x1, 1xn, or mx1 board: always one ship. The head-counting rule naturally handles these shapes.

The building blocks

1. Grid scanning with neighbor checks

The core pattern is iterating over a 2D grid and checking specific neighbors before making a decision:

for r in range(rows):
    for c in range(cols):
        if r > 0 and board[r - 1][c] == target:
            # neighbor above exists
        if c > 0 and board[r][c - 1] == target:
            # neighbor to the left exists

This same row-major scan with directional neighbor checks appears in Set Matrix Zeroes (marking rows and columns), Game of Life (counting live neighbors), and any grid problem where you process cells in a specific order and use previously-scanned cells to inform the current decision.

2. Canonical cell identification

Instead of using DFS to find all cells in a connected component, you identify one canonical representative per component. Here, the canonical cell is the top-left corner of each ship. This technique also appears in Number of Islands, where you could (in the case of well-separated islands) count only cells with no land above and no land to the left. The separation guarantee in this problem is what makes the shortcut work without full traversal.

From understanding to recall

The solution to Battleships in a Board is short, but the reasoning behind it is what matters. You need to internalize why counting heads works, why the separation constraint makes it safe, and why you do not need DFS. Under interview pressure, it is easy to default to the DFS approach and miss the O(1) space optimization.

Spaced repetition helps you lock in the pattern. You practice writing the scan loop and the two neighbor checks from scratch. After a few reps, the head-counting rule becomes automatic. You see a grid with non-overlapping objects and immediately think, "count canonical cells."

Related posts

• Number of Islands - The classic grid connected-component problem that teaches DFS flood fill, the approach this problem lets you skip
• Set Matrix Zeroes - Another in-place matrix problem where careful scanning order and neighbor relationships eliminate extra space
• Game of Life - Grid neighbor counting with in-place state encoding, a different take on processing cells based on their surroundings