LeetCode Medium: Battleships in a Board

Following 2 approaches (at-least) can be used to solve Problem #419: Battleships in a Board:

Approach 1: O(n^2) DFS Sinking, where n is the number fo cells in the board

class Solution {
    public int countBattleships(char[][] board) {
        int battleships = 0;
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[i].length; j++) {
                if (board[i][j]=='X') {
                    battleships++;
                    sink(board, i, j);
                }
            }
        }
        return battleships;
    }
    
    void sink(char[][] board, int i, int j) {
        if (i<0 || i>=board.length || j<0 || j>=board[i].length || board[i][j]!='X') {
            return;
        }
        
        board[i][j] = '.';
        sink (board, i+1, j);
        sink (board, i-1, j);
        sink (board, i, j+1);
        sink (board, i, j-1);
    }
}

Approach 2: Single Pass O(n), by counting only the head Xs of every battleship

class Solution {
    public int countBattleships(char[][] board) {
        int battleships = 0;
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[i].length; j++) {
                if (board[i][j]=='.' || (i>0 && board[i-1][j]=='X') || (j>0 && board[i][j-1]=='X'))
                    continue;
                battleships++;
            }
        }
        return battleships;
    }
}