LeetCode 419: Battleships in a Board

Problem Restatement

We are given a 2D board containing:

Battleships follow these rules:

1. Battleships are placed either horizontally or vertically.
2. Battleships cannot touch each other horizontally, vertically, or diagonally.
3. A battleship consists of one or more consecutive "X" cells.

Return the total number of battleships on the board.

The official follow-up asks whether we can solve the problem in one pass using only constant extra memory and without modifying the board. The constraints allow up to 200 x 200 boards. (leetcode.com)

Input and Output

Example function shape:

def countBattleships(board: list[list[str]]) -> int:
    ...

Examples

Example 1:

image_group{“layout”:“carousel”,“aspect_ratio”:“16:9”,“query”:[“leetcode 419 battleships in a board example”,“battleship board grid example”,“count battleships matrix illustration”,“horizontal and vertical battleship example”],“num_per_query”:1}

board = [
    ["X", ".", ".", "X"],
    [".", ".", ".", "X"],
    [".", ".", ".", "X"],
]

The answer is:

2

Explanation:

Example 2:

board = [["."]]

The answer is:

0

Example 3:

board = [["X"]]

The answer is:

1

First Thought: DFS or BFS

One natural approach is:

1. Scan the grid.
2. When we find an unvisited "X", start DFS or BFS.
3. Mark the whole ship as visited.
4. Increment the answer.

This works.

But the problem guarantees ships never touch each other.

That allows a simpler one-pass solution with constant extra space.

Key Insight

Every battleship has exactly one top-left starting cell.

For example:

X X X

The first cell is the ship start.

The later cells belong to the same ship.

Similarly:

X
X
X

Again, only the top cell is the start.

So while scanning the board:

A cell starts a new battleship exactly when:

1. The cell contains "X".
2. There is no "X" directly above it.
3. There is no "X" directly to its left.

That means this cell is the top-left corner of a ship.

Every battleship contributes exactly one such cell.

Algorithm

Initialize:

count = 0

Scan every cell (r, c).

For each cell:

1. If the cell is ".", skip it.
2. If the cell above is "X", skip it.
3. If the cell to the left is "X", skip it.
4. Otherwise, this cell is the start of a new battleship:
   • Increment count.

Return count.

Correctness

Consider any battleship on the board.

Because ships are straight horizontal or vertical segments, the battleship has exactly one top-leftmost cell.

For that cell:

1. There is no "X" above it.
2. There is no "X" to its left.

Therefore, the algorithm counts that cell.

Now consider any other cell belonging to the same battleship.

If the ship is horizontal, then that cell has an "X" to its left.

If the ship is vertical, then that cell has an "X" above it.

So the algorithm skips every non-start cell.

Thus each battleship is counted exactly once.

Since every counted cell corresponds to a unique battleship start, and every battleship has exactly one such start cell, the final count is correct.

Complexity

Here:

Implementation

from typing import List

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        rows = len(board)
        cols = 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

Code Explanation

We first get the board size:

rows = len(board)
cols = len(board[0])

The variable:

count

stores the number of battleships found.

We scan every cell:

for r in range(rows):
    for c in range(cols):

If the cell is empty water:

if board[r][c] == ".":
    continue

then it cannot start a battleship.

If the cell above is part of a ship:

if r > 0 and board[r - 1][c] == "X":
    continue

then the current cell belongs to the same vertical ship.

If the cell to the left is part of a ship:

if c > 0 and board[r][c - 1] == "X":
    continue

then the current cell belongs to the same horizontal ship.

If neither condition holds, this cell is the unique top-left start of a battleship:

count += 1

Finally:

return count

returns the total number of ships.

Alternative DFS Solution

A DFS approach also works.

from typing import List

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        rows = len(board)
        cols = len(board[0])

        visited = [[False] * cols for _ in range(rows)]

        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return

            if board[r][c] != "X":
                return

            if visited[r][c]:
                return

            visited[r][c] = True

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        ships = 0

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "X" and not visited[r][c]:
                    ships += 1
                    dfs(r, c)

        return ships

This version is easier to generalize, but it uses additional memory.

Testing

def test_count_battleships():
    s = Solution()

    board1 = [
        ["X", ".", ".", "X"],
        [".", ".", ".", "X"],
        [".", ".", ".", "X"],
    ]

    assert s.countBattleships(board1) == 2

    board2 = [["."]]

    assert s.countBattleships(board2) == 0

    board3 = [["X"]]

    assert s.countBattleships(board3) == 1

    board4 = [
        ["X", "X", ".", "X"],
        [".", ".", ".", "."],
        ["X", ".", "X", "X"],
    ]

    assert s.countBattleships(board4) == 4

    board5 = [
        ["X"],
        ["X"],
        ["X"],
    ]

    assert s.countBattleships(board5) == 1

    print("all tests passed")

Test Notes