algoadvance

Leetcode 419. Battleships in a Board

Problem Statement

You are given an m x n board where each cell is a battleship (‘X’) or water (‘.’). You need to find the number of battleships on the board. Battleships can only be placed horizontally or vertically on the board. In other words, they can only span an entire row or an entire column.

• There are no adjacent battleships (i.e., no horizontal or vertical adjacent cells containing battleships).

Write a function to count the number of battleships on a given board.

Example:

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

Clarifying Questions

1. Is there any restriction on the dimensions of the board?
   • No specific constraints were mentioned in the problem. We can assume the board can have variable dimensions.
2. Is it guaranteed that the input board will not contain invalid elements?
   • Yes, the problem statement guarantees that each cell will either be a battleship (‘X’) or water (‘.’).

Strategy

We can count the number of battleships by iterating through each cell of the board. For a cell containing a battleship (‘X’), we can count it as a new battleship if it is not part of an already accounted battleship above it or to its left. Specifically:

1. If the cell board[i][j] is ‘X’, we check:
   • If i > 0 and board[i-1][j] is ‘X’, then this ‘X’ is part of a battleship counted by a cell above it.
   • If j > 0 and board[i][j-1] is ‘X’, then this ‘X’ is part of a battleship counted by a cell to its left.
2. If neither condition is met, we consider the ‘X’ as the first cell of a new battleship and increment our count.

This approach ensures each battleship is counted exactly once.

Code

Here’s the implementation based on the strategy:

public class BattleshipsInABoard {
    public int countBattleships(char[][] board) {
        int count = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'X') {
                    if (i > 0 && board[i - 1][j] == 'X') {
                        continue;
                    }
                    if (j > 0 && board[i][j - 1] == 'X') {
                        continue;
                    }
                    count++;
                }
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
        BattleshipsInABoard solution = new BattleshipsInABoard();
        char[][] board = {
            {'X', '.', '.', 'X'},
            {'.', '.', '.', 'X'},
            {'.', '.', '.', 'X'}
        };
        System.out.println(solution.countBattleships(board)); // Output: 2
    }
}

Time Complexity

• Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the board. This is because we are iterating through each cell of the board exactly once.
• Space Complexity: O(1). No extra space is used that scales with input size; we are only using a limited number of extra variables.

This ensures the solution is both efficient and scalable for larger boards.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?