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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Battleships in a Board

Difficulty: Medium

Problem Description

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, and there must be at least one horizontal or vertical cell separating two battleships.

Key Insights

  • Battleships are formed by contiguous 'X' cells either in a row (horizontally) or a column (vertically).
  • To count the number of battleships, we can simply iterate through the board and count a new battleship when we encounter an 'X' that is either the first in its row or the first in its column.
  • We need to ensure that we do not double count any part of a battleship.

Space and Time Complexity

Time Complexity: O(m * n) - where m is the number of rows and n is the number of columns in the board. Space Complexity: O(1) - no extra space is used that scales with the input size.

Solution

To solve this problem, we can use a simple iteration approach. We'll traverse each cell in the board:

  1. If we encounter an 'X', we check if it's the start of a new battleship.
  2. A new battleship is identified if either:
    • It is in the first row (i == 0) or the cell directly above it is empty (board[i - 1][j] == '.').
    • It is in the first column (j == 0) or the cell directly to the left is empty (board[i][j - 1] == '.').
  3. Every time we find a new battleship, we increment our count.

This approach ensures we only count each battleship once, conforming to the problem constraints.

Code Solutions

def countBattleships(board):
    if not board:
        return 0

    count = 0
    m, n = len(board), len(board[0])

    for i in range(m):
        for j in range(n):
            if board[i][j] == 'X':
                # Check if it is the start of a new battleship
                if (i == 0 or board[i - 1][j] == '.') and (j == 0 or board[i][j - 1] == '.'):
                    count += 1

    return count
← Back to All Questions