LeetCode Problem 419

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Matrix

Solution

LeetCode 419 - Battleships in a Board

Problem Understanding

This problem gives us a two dimensional grid where each cell contains either 'X' or '.'.

An 'X' represents part of a battleship, while '.' represents empty water.

The important rule is that battleships are always placed in straight lines. A battleship can be:

• Horizontal, shaped like 1 x k
• Vertical, shaped like k x 1

This means battleships never bend or form rectangles.

The problem also guarantees that there is at least one empty cell separating any two battleships. Two ships are never directly adjacent horizontally or vertically.

Our task is to count how many distinct battleships exist on the board.

For example, consider:

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

The leftmost X is a single-cell battleship.

The vertical column on the right side forms another battleship.

Therefore the answer is 2.

The constraints tell us:

• The board dimensions can be up to 200 x 200

• A full scan of the board is completely feasible

• We should aim for an O(m * n) solution

• The follow up specifically asks for:

• One pass

• O(1) extra memory

• No modification of the board

These hints strongly suggest that we should avoid DFS visited arrays or flood fill approaches if possible.

Several edge cases are important:

• A board containing only water
• A board with a single cell
• Single-cell battleships
• Long horizontal ships
• Long vertical ships
• Multiple ships placed near each other diagonally
• Ships touching diagonally, which is allowed
• Large dense boards

A naive implementation can accidentally count multiple cells from the same ship as separate battleships. The key challenge is identifying when an 'X' represents the beginning of a ship versus merely another segment of an already counted ship.

Approaches

Brute Force Approach

A straightforward solution is to use Depth First Search or Breadth First Search.

Whenever we encounter an unvisited 'X', we start a traversal that explores all connected 'X' cells belonging to the same battleship. After finishing the traversal, we increment the battleship count by one.

This works because every connected component of 'X' cells corresponds to exactly one battleship under the problem constraints.

However, this approach requires additional memory:

• A visited matrix, or
• Modifying the input board

The DFS or BFS traversal also introduces unnecessary overhead because the board structure has very strong guarantees.

Although the complexity is acceptable for the constraints, it does not satisfy the follow up requirement of O(1) extra space without modifying the board.

Optimal Approach

The key observation is that we only need to count the starting cell of each battleship.

A cell is the start of a battleship if:

• The current cell contains 'X'
• There is no 'X' directly above it
• There is no 'X' directly to its left

Why does this work?

If a battleship is horizontal, every cell except the first one has another 'X' to its left.

If a battleship is vertical, every cell except the first one has another 'X' above it.

Therefore, the first cell of every ship is uniquely identified by the absence of adjacent ship cells above and to the left.

This allows us to count ships in a single pass with constant extra memory.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force DFS/BFS	O(m * n)	O(m * n)	Traverses connected ship components using visited tracking
Optimal Scan	O(m * n)	O(1)	Counts only ship starting cells

Algorithm Walkthrough

1. Initialize a counter variable battleships = 0.
2. Iterate through every cell in the board using nested loops.
3. For each cell, first check whether it contains 'X'.

If the cell contains '.', it cannot be part of a battleship, so we skip it. 4. If the current cell contains 'X', determine whether it is the start of a new ship.

We check:

• Is there an 'X' directly above?
• Is there an 'X' directly to the left?

5. If either neighbor contains 'X', then the current cell belongs to an already counted battleship.

This means:

• A horizontal ship continues from the left
• A vertical ship continues from above

6. If neither neighbor contains 'X', then this cell is the first segment of a new battleship.

Increment the counter. 7. Continue scanning until the entire board has been processed. 8. Return the final battleship count.

Why it works

Every battleship has exactly one top-leftmost cell.

For a horizontal ship, only the first cell lacks a left neighbor.

For a vertical ship, only the first cell lacks an upper neighbor.

Because ships never touch each other horizontally or vertically, every battleship contributes exactly one such starting cell. Therefore, counting these starting cells counts every battleship exactly once.

Python Solution

from typing import List

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

        battleships = 0

        for row in range(rows):
            for col in range(cols):
                if board[row][col] != 'X':
                    continue

                if row > 0 and board[row - 1][col] == 'X':
                    continue

                if col > 0 and board[row][col - 1] == 'X':
                    continue

                battleships += 1

        return battleships

The implementation begins by determining the number of rows and columns.

We then initialize a counter named battleships.

The nested loops scan every position in the matrix exactly once.

For each cell, the first condition checks whether the cell is actually part of a battleship. If not, we immediately continue to the next iteration.

Next, we check whether the current cell has another 'X' directly above it. If it does, this means the current cell belongs to a vertical battleship that has already been counted earlier.

Similarly, we check whether the current cell has another 'X' directly to its left. If so, it belongs to a horizontal battleship that has already been counted.

Only when neither condition is true do we increment the battleship count. This guarantees that each ship contributes exactly one count.

The algorithm never modifies the board and uses only constant extra memory.

Go Solution

func countBattleships(board [][]byte) int {
    rows := len(board)
    cols := len(board[0])

    battleships := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {

            if board[row][col] != 'X' {
                continue
            }

            if row > 0 && board[row-1][col] == 'X' {
                continue
            }

            if col > 0 && board[row][col-1] == 'X' {
                continue
            }

            battleships++
        }
    }

    return battleships
}

The Go implementation follows the exact same logic as the Python version.

The board is represented as [][]byte, so comparisons are made against byte literals like 'X'.

Go slices naturally provide dynamic access to rows and columns, so no additional handling is necessary.

There are no integer overflow concerns because the maximum number of cells is only 40,000.

The algorithm also uses constant extra memory in Go.

Worked Examples

Example 1

Input:

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

Board representation:

[
    ["X",".",".","X"],
    [".",".",".","X"],
    [".",".",".","X"]
]

We scan row by row.

Position	Value	Above X?	Left X?	Count Increment?	Total
(0,0)	X	No	No	Yes	1
(0,1)	.	-	-	No	1
(0,2)	.	-	-	No	1
(0,3)	X	No	No	Yes	2
(1,0)	.	-	-	No	2
(1,1)	.	-	-	No	2
(1,2)	.	-	-	No	2
(1,3)	X	Yes	No	No	2
(2,0)	.	-	-	No	2
(2,1)	.	-	-	No	2
(2,2)	.	-	-	No	2
(2,3)	X	Yes	No	No	2

Final answer:

2

Example 2

Input:

[
    ["."]
]

Traversal:

Position	Value	Count Increment?	Total
(0,0)	.	No	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Every cell is visited exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a constant amount of work for every cell in the matrix. Since there are m * n cells, the total running time is linear in the size of the board.

No auxiliary data structures such as queues, stacks, or visited matrices are required, so the extra memory usage remains constant.

Test Cases

from typing import List

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

        battleships = 0

        for row in range(rows):
            for col in range(cols):
                if board[row][col] != 'X':
                    continue

                if row > 0 and board[row - 1][col] == 'X':
                    continue

                if col > 0 and board[row][col - 1] == 'X':
                    continue

                battleships += 1

        return battleships

solution = Solution()

# Example 1
assert solution.countBattleships([
    ["X", ".", ".", "X"],
    [".", ".", ".", "X"],
    [".", ".", ".", "X"]
]) == 2  # Two separate battleships

# Example 2
assert solution.countBattleships([
    ["."]
]) == 0  # Empty board

# Single battleship cell
assert solution.countBattleships([
    ["X"]
]) == 1  # One single-cell ship

# Horizontal battleship
assert solution.countBattleships([
    ["X", "X", "X", "X"]
]) == 1  # One horizontal ship

# Vertical battleship
assert solution.countBattleships([
    ["X"],
    ["X"],
    ["X"]
]) == 1  # One vertical ship

# Multiple isolated ships
assert solution.countBattleships([
    ["X", ".", "X"],
    [".", ".", "."],
    ["X", ".", "X"]
]) == 4  # Four isolated ships

# Diagonal adjacency is allowed
assert solution.countBattleships([
    ["X", "."],
    [".", "X"]
]) == 2  # Two separate diagonal ships

# Mixed horizontal and vertical ships
assert solution.countBattleships([
    ["X", "X", ".", "."],
    [".", ".", ".", "X"],
    ["X", ".", ".", "X"],
    ["X", ".", ".", "."]
]) == 3  # Combination of ship shapes

# Large empty board
assert solution.countBattleships([
    [".", ".", "."],
    [".", ".", "."],
    [".", ".", "."]
]) == 0  # No ships anywhere

# Dense but valid placement
assert solution.countBattleships([
    ["X", ".", "X", ".", "X"],
    [".", ".", ".", ".", "."],
    ["X", ".", "X", ".", "X"]
]) == 6  # Many isolated ships

Test Summary

Test	Why
Example 1	Verifies mixed single and vertical ships
Example 2	Verifies completely empty board
Single cell ship	Tests smallest non-empty input
Horizontal battleship	Ensures left-neighbor logic works
Vertical battleship	Ensures upper-neighbor logic works
Multiple isolated ships	Verifies independent counting
Diagonal adjacency	Confirms diagonals do not merge ships
Mixed ship orientations	Tests combination scenarios
Large empty board	Verifies no false positives
Dense valid placement	Stress tests repeated counting logic

Edge Cases

Single Cell Board

A board with dimensions 1 x 1 is the smallest possible input. The single cell may contain either '.' or 'X'.

This case is easy to mishandle if boundary checks are not written carefully. Accessing row - 1 or col - 1 without verifying bounds could cause errors.

The implementation safely checks:

if row > 0
if col > 0

before accessing neighbors.

Long Horizontal or Vertical Ships

A ship may span an entire row or column.

A naive solution might incorrectly count every 'X' cell as a separate ship.

The algorithm avoids this by only counting cells that do not have an 'X' above or to the left. Every continuation segment is skipped automatically.

Diagonal Battleships

Ships are allowed to touch diagonally:

X.
.X

These are two separate ships, not one connected component.

Some graph traversal implementations accidentally treat diagonal adjacency as connected if all eight directions are explored.

This implementation only checks top and left neighbors, which correctly preserves the problem definition that ships connect only horizontally or vertically.