Problem

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).

Examples

Example 1:

1
2
3
4

Input:
board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output:
 2

Example 2:

1
2
3
4

Input:
board = [["."]]
Output:
 0

Solution

Method 1 – One Pass Counting

Intuition

A battleship is represented by consecutive ‘X’s horizontally or vertically, and ships are separated by at least one ‘.’ cell. We only count the top-left cell of each ship (a cell that is ‘X’ and has no ‘X’ above or to the left).

Approach

  1. Iterate through each cell in the board.
  2. If the cell is ‘X’ and there is no ‘X’ directly above or to the left, increment the count.
  3. Return the total count after scanning the board.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size(), ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) {
                    ans++;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func countBattleships(board [][]byte) int {
    m, n := len(board), len(board[0])
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X') {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length, n = board[0].length, ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) {
                    ans++;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun countBattleships(board: Array<CharArray>): Int {
        val m = board.size
        val n = board[0].size
        var ans = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) {
                    ans++
                }
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def countBattleships(self, board: list[list[str]]) -> int:
        m, n = len(board), len(board[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X' and (i == 0 or board[i-1][j] != 'X') and (j == 0 or board[i][j-1] != 'X'):
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn count_battleships(board: Vec<Vec<char>>) -> i32 {
        let m = board.len();
        let n = board[0].len();
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                if board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X') {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    countBattleships(board: string[][]): number {
        const m = board.length, n = board[0].length;
        let ans = 0;
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (board[i][j] === 'X' && (i === 0 || board[i-1][j] !== 'X') && (j === 0 || board[i][j-1] !== 'X')) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n), where m and n are the dimensions of the board, since each cell is visited once.
  • 🧺 Space complexity: O(1), as only a few variables are used for counting.

Method 2 – DFS Marking

Intuition

We can use DFS to mark all cells of a battleship as visited. For each unvisited ‘X’, start a DFS to mark the entire ship, and increment the count.

Approach

  1. Iterate through each cell in the board.
  2. If the cell is ‘X’, start a DFS to mark all connected ‘X’s as visited (change to ‘.’).
  3. Increment the count for each DFS call.
  4. Return the total count after scanning the board.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    void dfs(vector<vector<char>>& board, int i, int j) {
        int m = board.size(), n = board[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'X') return;
        board[i][j] = '.';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j+1);
        dfs(board, i, j-1);
    }
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size(), ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X') {
                    dfs(board, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func countBattleships(board [][]byte) int {
    m, n := len(board), len(board[0])
    var dfs func(int, int)
    dfs = func(i, j int) {
        if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'X' {
            return
        }
        board[i][j] = '.'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    }
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'X' {
                dfs(i, j)
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length, n = board[0].length, ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    dfs(board, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
    void dfs(char[][] board, int i, int j) {
        int m = board.length, n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'X') return;
        board[i][j] = '.';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j+1);
        dfs(board, i, j-1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun countBattleships(board: Array<CharArray>): Int {
        val m = board.size
        val n = board[0].size
        fun dfs(i: Int, j: Int) {
            if (i !in 0 until m || j !in 0 until n || board[i][j] != 'X') return
            board[i][j] = '.'
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        }
        var ans = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (board[i][j] == 'X') {
                    dfs(i, j)
                    ans++
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def countBattleships(self, board: list[list[str]]) -> int:
        m, n = len(board), len(board[0])
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'X':
                return
            board[i][j] = '.'
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X':
                    dfs(i, j)
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn count_battleships(board: &mut Vec<Vec<char>>) -> i32 {
        fn dfs(board: &mut Vec<Vec<char>>, i: i32, j: i32) {
            let m = board.len() as i32;
            let n = board[0].len() as i32;
            if i < 0 || i >= m || j < 0 || j >= n || board[i as usize][j as usize] != 'X' {
                return;
            }
            board[i as usize][j as usize] = '.';
            dfs(board, i+1, j);
            dfs(board, i-1, j);
            dfs(board, i, j+1);
            dfs(board, i, j-1);
        }
        let m = board.len();
        let n = board[0].len();
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                if board[i][j] == 'X' {
                    dfs(board, i as i32, j as i32);
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    countBattleships(board: string[][]): number {
        const m = board.length, n = board[0].length;
        function dfs(i: number, j: number) {
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== 'X') return;
            board[i][j] = '.';
            dfs(i+1, j);
            dfs(i-1, j);
            dfs(i, j+1);
            dfs(i, j-1);
        }
        let ans = 0;
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (board[i][j] === 'X') {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n), since each cell is visited at most once.
  • 🧺 Space complexity: O(m * n) in the worst case due to recursion stack.