Battleships In A Board - Leetcode Solution

Problem: You have a board with m rows and n columns, where each cell contains either a 0 or a 1. Starting from coordinate [0, 0], you take one step at a time in one of the four directions (up, down, left or right) until you reach the boundary of the board or an edge cell. Count the number of battleships on the board. Battleships are defined as any contiguous 1s that are not vertically or horizontally adjacent (i.e., they must not be positioned adjacent to each other in any of the four directions).

Solution: The key to this problem is to iterate through the matrix and count the number of battleships you encounter.

Algorithm:

1. Initialize a variable count to 0.
2. Loop through each cell in the matrix.
3. If a cell contains a 1, check if it is the first cell of a battleship by checking if the cell above it and the cell to its left contain a 0.
4. If it is the first cell of a battleship, increment the count.
5. After iterating through the matrix, return the count.

Code:

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        count = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X':
                    if (i == 0 or board[i-1][j] == '.') and (j == 0 or board[i][j-1] == '.'):
                        count += 1
        return count

Explanation: The code first initializes a variable count to 0. It then loops through each cell in the matrix using nested for-loops. If a cell contains a 1, the code checks if it is the first cell of a battleship by checking if the cell above it and the cell to its left contain a 0. If it is the first cell of a battleship, the count is incremented.

After iterating through the matrix, the function returns the count.

Time Complexity: The time complexity of this solution is O(n*m) where n is the number of columns and m is the number of rows in the matrix.

Space Complexity: The space complexity of this solution is O(1) since we are not using any additional data structures to solve the problem.

1