Abstract / Summary

Count the number of battleships on a grid by identifying valid ship placements in a board of Xs and dots.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 78% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Depth First Search
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The countBattleships method receives a two-dimensional list representing a rectangular board where each cell contains either "X" (part of a battleship) or "." (empty water). The method returns the total number of distinct battleships present on the board. Battleships are placed either horizontally or vertically, never diagonally, and they do not touch each other, even at corners. The algorithm walks the board once, identifies the start of each ship, expands in both possible directions to mark all its cells, and increments a counter for each new ship discovered.

Key Steps

Determining board dimensions

width  = len(board[0])
height = len(board)

The code extracts the number of columns (width) from the first row and the number of rows (height) from the outer list. These values drive the nested loops that traverse every coordinate.

Preparing traversal state

result = 0
seen   = set()

result holds the final ship count. seen is a set of coordinate tuples that have already been processed, ensuring that each cell is examined at most once.

Scanning each cell

for y in range(height):
    for x in range(width):
        if (x, y) in seen:
            continue
        seen.add((x, y))
        ...

The outer loop iterates over rows (y), the inner loop over columns (x). If a coordinate has been recorded in seen, the algorithm skips further work for that cell. Otherwise, the coordinate is added to seen to guarantee it will not be revisited later.

Detecting a new battleship

if board[y][x] == "X":
    result += 1
    ...

When the current cell contains "X" and has not been seen before, it marks the beginning of a new battleship. The counter is incremented immediately.

Extending horizontally

sx = x
while sx < width - 1 and board[y][sx + 1] == "X":
    sx += 1
    seen.add((sx, y))

Starting from the initial column x, the loop moves right while the next cell in the same row also contains "X". Each visited coordinate is added to seen so that later iterations will ignore those cells. The loop stops when it reaches the board edge or encounters a ".".

Extending vertically

sy = y
while sy < height - 1 and board[sy + 1][x] == "X":
    sy += 1
    seen.add((x, sy))

Similarly, this loop moves downward from the initial row y, adding each "X" cell in the same column to seen. The vertical expansion stops at the bottom edge or when a "." is found.

Returning the final count

return result

After all rows and columns have been processed, the method returns the accumulated number of distinct battleships.

Edge Cases Handled

The algorithm gracefully handles a board that contains only a single cell. If that cell is "X", the horizontal and vertical loops never execute because the conditions sx < width - 1 and sy < height - 1 are false, resulting in a correct count of one. When the board consists entirely of ".", the inner condition board[y][x] == "X" never triggers, leaving result at zero.

Ships that span the full length of a row or column are correctly processed. The horizontal loop continues until sx reaches width - 1, and the vertical loop proceeds until sy reaches height - 1. Because each visited cell is added to seen, subsequent outer-loop iterations that land on any part of the same ship will immediately skip further processing, preventing double counting.

Isolated ships that are separated by at least one empty cell in all directions are identified independently. The seen set ensures that only the first cell of each ship initiates counting, while all other cells belonging to that ship are ignored later.

Performance Optimizations

The use of a hash set (seen) to record processed coordinates eliminates the need for repeated scanning of cells that belong to already counted ships. By marking every cell of a discovered ship during its horizontal and vertical expansion, the algorithm guarantees that each board position is examined at most once, achieving linear work relative to the number of cells.

The early continue statement for already-seen coordinates prevents unnecessary branching and reduces the number of condition checks inside the inner loop. Adding the current coordinate to seen before any further logic ensures that even a solitary "." cell is never revisited, keeping the traversal tight.

Horizontal and vertical expansions are performed with simple while loops that stop as soon as a non-ship cell or board boundary is encountered. This localized scanning avoids scanning beyond the actual length of a ship, saving iterations especially when ships are short compared to the board dimensions.

Imagine a big square grid that is filled with toy battleships hidden in the water. Some spots in the grid are just blue water, and some spots have pieces of a ship marked with the letter X. To find how many ships are floating in this game, the computer works like a little detective walking through every single square one by one.

When the computer lands on a spot, it first checks if it has already looked there before. If the spot is new and has an X, it means a ship has been found, so the count goes up by one. After finding that piece, the computer looks to the left, right, up, and down to see if that ship continues into the next squares. If it finds more pieces of the same ship, it marks those squares off on a special list so it knows not to count them as new ships later. This way, every single long ship is counted as just one unit, and the computer can finish the game knowing exactly how many boats are hiding in the water.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python							TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python						Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	gouthampradhan		Java
	halfrost									Go
	JoshCrozier								JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	lzl124631x	C++
	martianoff					Scala
	ruoru						Rust
	suxrobGM				C#
	trung-hn			Python
	varunu28		Java
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
lzl124631x	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality