Last updated on January 13th, 2025 at 09:34 pm
Here, we see a Battleships in a Board LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array
Companies
Microsoft
Level of Question
Medium
Battleships in a Board LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Islands”. This pattern is commonly used to solve problems where you need to count or identify distinct groups or clusters in a 2D grid. In this case, the code is counting distinct battleships on a board, where battleships are represented as contiguous ‘X’ characters.
3. Code Implementation in Different Languages
3.1 Battleships in a Board C++
struct Solution {
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 ('X' == board[i][j] && (!i || '.' == board[i - 1][j]) && (!j || '.' == board[i][j - 1]))
ans++;
return ans;
}
};
3.2 Battleships in a Board Java
class Solution {
public int countBattleships(char[][] board) {
if (board == null) {
throw new IllegalArgumentException("Input is null");
}
if (board.length == 0 || board[0].length == 0) {
return 0;
}
int rows = board.length;
int cols = board[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'X'
&& (j == cols - 1 || board[i][j + 1] == '.')
&& (i == rows - 1 || board[i + 1][j] == '.')) {
count++;
}
}
}
return count;
}
}
3.3 Battleships in a Board JavaScript
var countBattleships = function(board) {
let count = 0;
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[i].length; j++) {
if (board[i][j] === 'X' && board[i][j-1] !== 'X' && (!board[i-1] || board[i-1][j] !== 'X')) count++;
}
}
return count;
};
3.4 Battleships in a Board Python
class Solution(object):
def countBattleships(self, board):
count = 0
for i, row in enumerate(board):
for j, cell in enumerate(row):
if cell == "X":
if (i == 0 or board[i - 1][j] == ".") and\
(j == 0 or board[i][j - 1] == "."):
count += 1
return count
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(m * n) | O(1) |
| Java | O(m * n) | O(1) |
| JavaScript | O(m * n) | O(1) |
| Python | O(m * n) | O(1) |
- The code is efficient as it processes each cell only once.
- It avoids unnecessary checks by leveraging the conditions for the first cell of a battleship.
- The implementation is consistent across all languages, with minor syntactic differences.