algoadvance

You are given an m x n matrix board where each cell is a battleship (‘X’) or water (‘.’). The battleships on the board are represented by ‘X’s, and empty slots are represented by ‘.’s. You need to count the number of battleships on the board.

Battleships can only be placed horizontally or vertically on the board. In other words, they can only be made up of ‘X’s that are adjacent horizontally or vertically. The same battleship will not be adjacent to another battleship, meaning there will be no adjacent ‘X’s horizontally or vertically.

Return the number of battleships on the board.

Example:

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

Clarifying Questions

  1. Can there be a battleship that spans multiple rows or columns, beyond just 1 row or 1 column straight line?
    • Yes, a battleship can span multiple slots but still needs to be in a single row or a single column.
  2. Do diagonally adjacent ‘X’s count as the same battleship?
    • No, they do not. Battleships are only horizontal or vertical.
  3. Do we need to alter the original board during the calculation?
    • No, altering the board is not necessary.

Strategy

The strategy to solve this problem involves iterating through each cell of the board. We will count only the ‘X’s that are the starting point of a battleship.

Code

Let’s implement the strategy now:

def countBattleships(board):
    if not board:  # Edge case: empty board
        return 0

    rows = len(board)
    cols = len(board[0])
    count = 0

    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'X':
                # Check if it's the start of a battleship
                if (i == 0 or board[i-1][j] == '.') and (j == 0 or board[j][j-1] == '.'):
                    count += 1
    return count

# Example Usage
board = [
  ["X", ".", ".", "X"],
  [".", ".", ".", "X"],
  [".", ".", ".", "X"]
]
print(countBattleships(board))  # Output: 2

Time Complexity

The time complexity of this solution is (O(m \times n)), where (m) is the number of rows and (n) is the number of columns in the board. This is because we need to iterate through each cell of the board exactly once.

Space Complexity

The space complexity is (O(1)) as we are using only a constant amount of extra space beyond the input matrix.

Try our interview co-pilot at AlgoAdvance.com