[Google Question] Count Battleships in a Board

Problem: Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
• At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

X..X
...X
X...    Output: 3, In this board there are 3 battleships.

Approach: There are multiple approaches we can use to solve this problem. We can use another 2D bool matrix to keep the state of a cell (i, j) to see if (i, j] is already visited or not so in this case the algorithm will look like:

• num_battleships = 0
• FOR i = 0 to num_rows
• FOR j = 0 to num_columns
• IF board[i][j] == 'X' AND !visited[i][j] 
• num_battleships = num_battleships + 1
• visited[i][j] = true
• IF board[i + 1][j] = 'X'
• FOR k = i + 1 to till board[k][j] = 'X' or num_rows
• visited[k][j] = true
• ELSE IF board[i][j + 1] == 'X'
• FOR k = j + 1 to till board[i][k] = 'X' or num_columns
• visited[i][k] = ture
• RETURN num_battleships

This will work and will solve the problem in O(n^2) which we can't improve but this is taking O(n^2) space. Let's see how we can reduce it.

Instead of taking extra space to store the state, we can just replace 'X' to '.' once we visited the cell. In that way we will never consider the same cell again. So now our algorithm looks like:

• num_battleships = 0
• FOR i = 0 to num_rows
• FOR j = 0 to num_columns
• IF board[i][j] == 'X' 
• num_battleships = num_battleships + 1
• board[i][j] = '.'
• IF board[i + 1][j] = 'X'
• FOR k = i + 1 to till board[k][j] = 'X' or num_rows
• board[k][j] = '.'
• ELSE IF board[i][j + 1] == 'X'
• FOR k = j + 1 to till board[i][k] = 'X' or num_columns
• board[i][k] = '.'
• RETURN num_battleships

This is a optimal solution which runs in O(n^2) time and uses no extra storage. But if you see we are modifying the original board, what if it is not allowed then either we can fallback to our extra space solution or we can find a better solution? Let's see:

If for any cell (i, j) we find board[i][j] = X then we can check for board[i - 1][j] or board[i][j - 1] and if we find any of these value 'X' then we are sure that cell (i, j) is part of a battleship which we have already counted. With this approach, here is another algorithm:

• num_battleships = 0
• FOR i = 0 to num_rows
• FOR j = 0 to num_columns
• IF board[i][j] == '.'
• continue
• IF board[i - 1][j] == 'X'
• continue
• IF board[i][j  - 1] == 'X'
• continue
• num_battleships = num_battleships + 1
• RETURN num_battleships

Please note that in each of the algorithm shown above, I haven't handle the corner cases just to make them easy to understand. You can understand the edge cases handling in the implementation itself.

 

Implementation in C#:

        public int CountBattleships(char[][] board)

        {

            int numBattleShips = 0;

            for (int i = 0; i < board.Length; ++i)

            {

                for (int j = 0; j < board[0].Length; ++j)

                {

                    if (board[i][j] == '.' || (i > 0 && board[i - 1][j] == 'X') || (j > 0 && board[i][j - 1] == 'X'))

                    {

                        continue;

                    }

                    ++numBattleShips;

                }

            }

            return numBattleShips;

        }

Complexity: O(n ^ 2)