Battleships in a Board — Solution in Python, Java & C++
Battleships in a Board solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Battleships in a Board is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
board is an m x n grid given as m strings, where 'X' is part of a battleship and '.' is open water.
Every battleship is a straight line of cells: 1 x k (horizontal) or k x 1 (vertical) for some k >= 1. Two battleships never touch along an edge — at least one water cell separates them horizontally and vertically (they may meet diagonally).
Return the number of battleships on the board.
Example 1
Input: board = ["X..X","...X","XX.X"]
Output: 3
Explanation: A single-cell ship at the top-left, a vertical ship in the last column and a horizontal ship of length 2 at the bottom-left.
Example 2
Input: board = ["."]
Output: 0
Example 3
Input: board = ["X.X",".X."]
Output: 3
Explanation: Ships that meet only at corners are separate ships.
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j] is 'X' or '.'the board is a valid arrangement of battleships
Follow-up: Can you count them in one pass with O(1) extra memory and without modifying the board?
Hints for Battleships in a Board
Hint 1
Flood-filling each group of
'X'cells works, but the shapes are so restricted that you do not need to.Hint 2
Every ship has exactly one top-left cell — its first cell in reading order.
Hint 3
Count the
'X'cells whose upper neighbour and left neighbour are both not'X'.
How to solve Battleships in a Board
Count each ship once at its head — the cell with no 'X' directly above it or directly to its left.
Approach
- Scan every cell
(i, j). - Skip it unless it is
'X'. - Skip it if
(i-1, j)is'X'or(i, j-1)is'X'— it continues a ship already counted. - Otherwise add one.
Why it works
A horizontal ship's cells, other than the first, all have an 'X' to their left; a vertical ship's have one above. The first cell of a ship has neither, because ships are straight and no other ship touches it along an edge. So exactly one cell per ship passes the test.
Complexity
- Time —
O(m · n) - Space —
O(1)
Pitfalls
- Diagonal neighbours do not join ships — check only above and to the left.
- Guard the first row and the first column before looking up or left.
- This trick relies on the board being valid; on arbitrary shapes you would need a flood fill.
Reference solution
Python
from typing import List
def countBattleships(board: List[str]) -> int:
ships = 0
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] != 'X':
continue
if i > 0 and board[i - 1][j] == 'X':
continue
if j > 0 and board[i][j - 1] == 'X':
continue
ships += 1
return shipsJava
public static int countBattleships(String[] board) {
int ships = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length(); j++) {
if (board[i].charAt(j) != 'X') continue;
if (i > 0 && board[i - 1].charAt(j) == 'X') continue;
if (j > 0 && board[i].charAt(j - 1) == 'X') continue;
ships++;
}
}
return ships;
}C++
int countBattleships(vector<string>& board) {
int ships = 0;
for (int i = 0; i < (int)board.size(); i++) {
for (int j = 0; j < (int)board[i].size(); j++) {
if (board[i][j] != 'X') continue;
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
ships++;
}
}
return ships;
}JavaScript
var countBattleships = function(board) {
var ships = 0;
for (var i = 0; i < board.length; i++) {
for (var j = 0; j < board[i].length; j++) {
if (board[i][j] !== 'X') continue;
if (i > 0 && board[i - 1][j] === 'X') continue;
if (j > 0 && board[i][j - 1] === 'X') continue;
ships++;
}
}
return ships;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)