Battleships in a Board - Solution & Explanation
Problem Statement
Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board.
Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).
Example 1:
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]] Output: 2
Example 2:
Input: board = [["."]] Output: 0
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j]is either'.'or'X'.
Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the values board?
Approach Overview
Problem Overview: You are given an m x n grid representing a battleship board. Cells contain either 'X' (part of a ship) or '.' (empty). Ships are placed only horizontally or vertically and never touch each other. The task is to count how many distinct battleships exist on the board.
Approach 1: Brute Force DFS Traversal (O(m*n) time, O(m*n) space)
Treat the board as a graph and explore each ship using Depth-First Search. Iterate through every cell of the matrix. When you encounter an 'X' that hasn't been visited, start a DFS and mark all connected 'X' cells belonging to that ship. Because ships are guaranteed to be straight lines, the DFS will only extend horizontally or vertically. Maintain a visited structure (array or hash set) to avoid revisiting cells. Each DFS traversal corresponds to exactly one battleship, so increment the count when a new traversal begins. This approach is straightforward and mirrors typical Depth-First Search problems on grids.
Approach 2: Optimized Linear Scan (O(m*n) time, O(1) space)
A more efficient observation eliminates the need for DFS or extra memory. Instead of exploring entire ships, count only the starting cell of each battleship. A cell is the start of a ship if it contains 'X' and there is no 'X' directly above it and no 'X' directly to its left. Iterate through the grid once using simple array indexing. When a cell satisfies this condition, it must represent the top-left segment of a battleship, so increment the count. All other segments belong to ships already counted. This works because ships never touch and are always straight lines.
Recommended for interviews: The optimized linear scan is what interviewers expect. It shows you can recognize structural constraints in the grid and reduce the problem to a single pass with O(1) extra space. Explaining the DFS approach first demonstrates understanding of grid traversal, but identifying the start-cell trick highlights stronger problem-solving skills.
Approach 1: Brute Force Approach
This approach involves iterating over all possible pairs in the list and checking each possible solution. It's not the most efficient but lays a good groundwork to understand the problem.
The C solution iterates over the array with two loops, checking each pair. The inner logic within the nested loop is where you'd handle any conditions specific to the problem.
Complexity
Time Complexity: O(n^2) where n is the number of elements in the array.
Space Complexity: O(1) as we are using a fixed amount of extra space.
Approach 2: Optimized Hash Map Approach
This approach uses a hash map to store and track information about the elements, allowing us to reduce the number of comparisons by enabling constant time lookups. It leverages the hash map to quickly determine if another element needed to meet the condition exists.
The C solution uses a simple hashing mechanism with an array acting as a hash table to record the presence of elements, which can then be used to efficiently find elements meeting certain conditions.
Complexity
Time Complexity: O(n) on average, assuming simple hash function.
Space Complexity: O(n) for the hash table storage.
Approach 3: Direct Iteration
We can iterate through the matrix, find the top-left corner of each battleship, i.e., the position where the current position is X and both the top and left are not X, and increment the answer by one.
After the iteration ends, return the answer.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) where n is the number of elements in the array. |
| Optimized Hash Map Approach | Time Complexity: O(n) on average, assuming simple hash function. |
| Direct Iteration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS Traversal | O(m*n) | O(m*n) | When learning grid traversal or when ships could have arbitrary shapes requiring full exploration |
| Optimized Linear Scan (Start Cell Detection) | O(m*n) | O(1) | Best approach when ships are guaranteed to be straight and non-touching |
Video Solution
Battleships in a Board • Kevin Naughton Jr. • 40,286 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Battleships in a Board easy or hard?
Battleships in a Board Python/Java solution
How to solve Battleships in a Board in O(n)?
What is the best approach for Battleships in a Board?
Is Battleships in a Board asked at Google/Amazon/Meta?
What data structure is used in Battleships in a Board?
What is the time complexity of Battleships in a Board?
Ready to solve this problem?
Practice Battleships in a Board with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor