Note that the question mentions that you’re only given valid input. So between each battle ship, there has to be a .. The task is to identify number of battleships where each battleship is consecutive X either horizontally or vertically. This can be done easily by using extra space of by changing the input array. Let’s see a solution where we neither have to use extra space or change the input array. We take advantage of the fact that we are only given valid boards. We will start iterating with two pointers, i (row) and j (column), from [0,0] index normally as we do. Notice that whenever we encounter an ‘X’ and the next element in its row (board[i+1][j]) or column (board[i][j+1]) is an ‘X’ then this element is not the last element of battleship. Our aim is to only update the battleship count whenever we encounter the last element in the battleship. Now, if the element is ‘X’ but board[i+1][j] or board[i][j+1] is not ‘X’, that means that this is the last element in the battleship. We will update the count.
Note that this works only because no battleship shares a common ‘X’. Consider this:
Valid board:
X*..X
...X
...X*
* marked X are when we update our battleship count by the above logic.
Invalid board:
...X
XXXX
...X*
Here, our answer would come out to be 1. But this is an invalid board as battleships will always have a cell separating between them so we do not bother.
int countBattleships(vector<vector<char>>& board) {
int r = board.size(), c = board[0].size(), res=0;
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
if (board[i][j] == '.')
continue;
if (i+1<r && board[i+1][j] == 'X')
continue;
if (j+1<c && board[i][j+1] == 'X')
continue;
res++;
}
}
return res;
}
Time complexity: O(r*c)
Space complexity: O(1)