Battleships in a Board
Medium · Graphs · Explanation and code example
Count Only Ship Starts
How it works
A horizontal or vertical ship has exactly one cell with no ship cell immediately above or to its left. Count those starts while scanning the board. The guaranteed separation between ships makes this local test sufficient, without marking cells.
Steps
- Skip empty cells.
- Skip an X with an X above or left.
- Count every remaining X as a new ship.
Complexity
- Time: O(rows × columns).
- Space: O(1).
Things to watch for
- This relies on valid separated horizontal or vertical ships.
- Do not count every X.
- The board is read without mutation.
Python code example
class Solution:
def countBattleships(self, board: list[list[str]]) -> int:
ans = 0
for i, row in enumerate(board):
for j, cell in enumerate(row):
if cell == '.':
continue
if i > 0 and board[i - 1][j] == 'X':
continue
if j > 0 and board[i][j - 1] == 'X':
continue
ans += 1
return ans
C++ code example
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int ans = 0;
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] == '.')
continue;
if (i > 0 && board[i - 1][j] == 'X')
continue;
if (j > 0 && board[i][j - 1] == 'X')
continue;
++ans;
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.