We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Battleships in a Board

Number: 419

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Microstrategy, Google, Tinkoff, Microsoft

Problem Description

Given an m x n board, count the number of battleships on the board. Each battleship is represented by contiguous 'X's placed either horizontally or vertically. Battleships are separated by at least one empty cell ('.') in all directions, so if an 'X' has another 'X' above or to its left, it is part of an already counted battleship.

Key Insights

  • A battleship is represented as a contiguous line (either 1 x k or k x 1) of 'X's.
  • Since battleships are not adjacent, you can count an 'X' only if there is no 'X' directly above or to the left.
  • This check ensures that you count the battleship only once, at its "start" cell.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(1) as no additional data structures are used.

Solution

Traverse the board once. For each cell:

  • If the cell contains '.', continue.
  • If the cell contains 'X', check:
    • If there is an 'X' directly above, it is part of an already counted vertical battleship.
    • If there is an 'X' directly to the left, it is part of an already counted horizontal battleship.
  • Only increment your counter for battleships if both conditions are false.
  • This one-pass solution satisfies the requirement of constant extra space and no modification to the board.

Code Solutions

# Function to count battleships in a board
def countBattleships(board):
    # Initialize counter for battleships
    count = 0
    # Get dimensions of the board
    rows = len(board)
    cols = len(board[0])
    
    # Iterate over each cell in the board
    for i in range(rows):
        for j in range(cols):
            # Skip if cell is not a battleship part
            if board[i][j] == '.':
                continue
            # If there is 'X' above, it is part of an existing battleship
            if i > 0 and board[i - 1][j] == 'X':
                continue
            # If there is 'X' to the left, it is part of an existing battleship
            if j > 0 and board[i][j - 1] == 'X':
                continue
            # Else, count this cell as the start of a new battleship
            count += 1
    # Return the total count of battleships found
    return count

# Example usage:
board = [["X",".",".","X"],
         [".",".",".","X"],
         [".",".",".","X"]]
print(countBattleships(board))  # Expected output: 2
← Back to All Questions