Jobs

Interviews

Discussions

Battleships in a Board

Medium

Battleships in a Board

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters will represent a battleship and an empty cell? Can I assume that only 'X' represents a battleship and '.' represents an empty cell?
Can battleships wrap around the board edges or are they guaranteed to be fully contained within the grid?
Will the battleships be guaranteed to be separated by at least one horizontal or vertical cell, or can they be adjacent diagonally?
Is the input board guaranteed to be rectangular, or could it be ragged?
What are the maximum dimensions of the board? Is there a size limit that I should consider for memory allocation?

Brute Force Solution

Approach

We're given a grid where some cells contain parts of battleships. The brute force method involves carefully examining each cell to find and count these battleships. We need to be thorough and avoid counting the same ship multiple times.

Here's how the algorithm would work step-by-step:

Start at the very first cell in the grid.
Check if that cell contains part of a battleship.
If it does, then we've potentially found a new battleship.
To confirm, we explore all adjacent cells (to the right and below) to see if they also contain parts of the same battleship. We only explore right and down to avoid double counting.
Once we've explored the entire battleship and marked all its parts, we increment our battleship count.
Continue this process, moving cell by cell across the entire grid, checking each cell for a potential battleship.
If a cell contains part of a battleship that we've already counted, we simply skip it.
After checking every single cell in the grid, the final battleship count is the total number of distinct battleships found.

Code Implementation

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

    number_of_rows = len(board)
    number_of_columns = len(board[0])
    battleship_count = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'X':
                # Found a potential battleship

                battleship_count += 1
                sink_battleship(board, row_index, column_index, number_of_rows, number_of_columns)

    return battleship_count

def sink_battleship(board, row_index, column_index, number_of_rows, number_of_columns):
    # Mark the current cell as visited to avoid double-counting.
    board[row_index][column_index] = '.'

    # Explore right
    if column_index + 1 < number_of_columns and board[row_index][column_index + 1] == 'X':
        sink_battleship(board, row_index, column_index + 1, number_of_rows, number_of_columns)

    # Explore down
    if row_index + 1 < number_of_rows and board[row_index + 1][column_index] == 'X':
        # Explore down if there is a ship
        sink_battleship(board, row_index + 1, column_index, number_of_rows, number_of_columns)

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each cell of the m x n grid. For each cell containing a battleship part 'X', it explores the connected components of the battleship by only checking right and down. In the worst-case scenario, each cell might be visited once while exploring a battleship, and we visit each cell in the grid at least once. Thus, the time complexity is proportional to the number of cells in the grid, leading to O(m*n) where m and n are the dimensions of the grid.

Space Complexity

O(1) – The provided solution involves iterating through the grid and potentially marking cells of a battleship as visited implicitly by modifying the input. There is no auxiliary data structure mentioned that grows with the input grid size N (where N is the total number of cells in the grid, rows * cols). The battleship count is a single integer. Thus, the space complexity is constant.

Optimal Solution

Approach

The goal is to count the number of battleships in a given board. The key idea is to only count the 'head' of each battleship to avoid overcounting and ensure efficiency.

Here's how the algorithm would work step-by-step:

Go through each square in the board, one by one.
For each square, check if it contains a part of a battleship.
If it's a battleship part, check if it's the 'head' of the battleship. A square is a 'head' if the squares immediately above it and to its left are not also battleship parts.
If it's the 'head', then increment the battleship count.
Continue until every square is checked, and the final count is the number of battleships.

Code Implementation

def count_battleships(board):
    number_of_rows = len(board)
    number_of_columns = len(board[0]) if number_of_rows > 0 else 0
    battleship_count = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'X':
                # Check if current cell is the 'head' of a battleship.
                if (row_index > 0 and board[row_index - 1][column_index] == 'X'):
                    continue

                if (column_index > 0 and board[row_index][column_index - 1] == 'X'):
                    continue

                # Increment battleship_count if it's the 'head'.
                battleship_count += 1

    return battleship_count

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each cell in the board. Assuming the board has m rows and n columns, the algorithm visits each of the m*n cells exactly once. For each cell, it performs a constant number of checks (checking the cell above and to the left). Therefore, the time complexity is proportional to the number of cells in the board which is m*n. Hence the overall time complexity is O(m*n).

Space Complexity

O(1) – The algorithm iterates through the board and uses a constant number of variables to store the current row and column indices, and the battleship count. No auxiliary data structures such as lists, sets, or maps are created. Therefore, the extra space used by the algorithm remains constant irrespective of the board size (number of rows and columns), making the space complexity O(1).

Edge Cases

Case	How to Handle
Null or empty board	Return 0 if the board is null or has zero rows/columns.
Board with zero width or zero height	Return 0 because a battleship cannot exist without at least one cell.
Board containing only '.' characters	Return 0 as there are no battleships.
Board containing only 'X' characters representing a single large battleship	Count as one battleship when no adjacent 'X' are present (edge case for naive counting).
Battleship segments are not connected horizontally or vertically (e.g., diagonal 'X's)	Only count connected horizontal/vertical segments as part of a battleship, ignoring diagonals.
Invalid board where battleships touch each other	The problem statement implicitly assumes valid boards so this edge case doesn't need to be handled specifically beyond incorrect counts.
Board with a single row or single column	Handle by iterating through the row or column and counting battleships correctly.
Integer overflow if board size is extremely large	Ensure data types (e.g., counters) are large enough to handle potential board sizes; if the dimensions are constrained, no special action is needed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters will represent a battleship and an empty cell? Can I assume that only 'X' represents a battleship and '.' represents an empty cell?
Can battleships wrap around the board edges or are they guaranteed to be fully contained within the grid?
Will the battleships be guaranteed to be separated by at least one horizontal or vertical cell, or can they be adjacent diagonally?
Is the input board guaranteed to be rectangular, or could it be ragged?
What are the maximum dimensions of the board? Is there a size limit that I should consider for memory allocation?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very first cell in the grid.
Check if that cell contains part of a battleship.
If it does, then we've potentially found a new battleship.
To confirm, we explore all adjacent cells (to the right and below) to see if they also contain parts of the same battleship. We only explore right and down to avoid double counting.
Once we've explored the entire battleship and marked all its parts, we increment our battleship count.
Continue this process, moving cell by cell across the entire grid, checking each cell for a potential battleship.
If a cell contains part of a battleship that we've already counted, we simply skip it.
After checking every single cell in the grid, the final battleship count is the total number of distinct battleships found.

Code Implementation

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

    number_of_rows = len(board)
    number_of_columns = len(board[0])
    battleship_count = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'X':
                # Found a potential battleship

                battleship_count += 1
                sink_battleship(board, row_index, column_index, number_of_rows, number_of_columns)

    return battleship_count

def sink_battleship(board, row_index, column_index, number_of_rows, number_of_columns):
    # Mark the current cell as visited to avoid double-counting.
    board[row_index][column_index] = '.'

    # Explore right
    if column_index + 1 < number_of_columns and board[row_index][column_index + 1] == 'X':
        sink_battleship(board, row_index, column_index + 1, number_of_rows, number_of_columns)

    # Explore down
    if row_index + 1 < number_of_rows and board[row_index + 1][column_index] == 'X':
        # Explore down if there is a ship
        sink_battleship(board, row_index + 1, column_index, number_of_rows, number_of_columns)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to count the number of battleships in a given board. The key idea is to only count the 'head' of each battleship to avoid overcounting and ensure efficiency.

Here's how the algorithm would work step-by-step:

Go through each square in the board, one by one.
For each square, check if it contains a part of a battleship.
If it's a battleship part, check if it's the 'head' of the battleship. A square is a 'head' if the squares immediately above it and to its left are not also battleship parts.
If it's the 'head', then increment the battleship count.
Continue until every square is checked, and the final count is the number of battleships.

Code Implementation

def count_battleships(board):
    number_of_rows = len(board)
    number_of_columns = len(board[0]) if number_of_rows > 0 else 0
    battleship_count = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'X':
                # Check if current cell is the 'head' of a battleship.
                if (row_index > 0 and board[row_index - 1][column_index] == 'X'):
                    continue

                if (column_index > 0 and board[row_index][column_index - 1] == 'X'):
                    continue

                # Increment battleship_count if it's the 'head'.
                battleship_count += 1

    return battleship_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty board	Return 0 if the board is null or has zero rows/columns.
Board with zero width or zero height	Return 0 because a battleship cannot exist without at least one cell.
Board containing only '.' characters	Return 0 as there are no battleships.
Board containing only 'X' characters representing a single large battleship	Count as one battleship when no adjacent 'X' are present (edge case for naive counting).
Battleship segments are not connected horizontally or vertically (e.g., diagonal 'X's)	Only count connected horizontal/vertical segments as part of a battleship, ignoring diagonals.
Invalid board where battleships touch each other	The problem statement implicitly assumes valid boards so this edge case doesn't need to be handled specifically beyond incorrect counts.
Board with a single row or single column	Handle by iterating through the row or column and counting battleships correctly.
Integer overflow if board size is extremely large	Ensure data types (e.g., counters) are large enough to handle potential board sizes; if the dimensions are constrained, no special action is needed.