C++ 3ms 6 lines solution with runtime O(n) and space O(1)


  • 8

    Idea is to define upper left X as the head of battle ship. We simply need to count the number of heads.

    int countBattleships(vector<vector<char>>& board) {
            if (board.empty() || board[0].empty()) { return 0; }
            int m = board.size(), n = board[0].size(), cnt = 0;
            
            for (int r = 0; r < m; r++)
                for (int c = 0; c < n; c++)
                    cnt += board[r][c] == 'X' && (r == 0 || board[r - 1][c] != 'X') && (c == 0 || board[r][c - 1] != 'X');
            
            return cnt;
    }
    

  • 0
    O

    Thank you for the answer! I have a question that why I write (r == 0 || board[r][c-1] != 'X') && (c == 0 || board[r-1][c] != 'X') it shows runtime error but (r == 0 || board[r-1][c] != 'X') && (c == 0 || board[r][c-1] != 'X') works fine?


  • 1

    @owenxbw93
    Because (r == 0 || board[r][c-1] != 'X') && (c == 0 || board[r-1][c] != 'X') can't guarantee c-1 or r-1 are always non-negative.


  • 0
    S

    @soamaaazing Thanks for your solution! I'm thinking on how to deal with situation when it is negative.
    (r == 0 || board[r - 1][c] != 'X' ) This is really awesome!


  • 0
    V

    hard to read imo..


  • 0
    S

    @owenxbw93 for (r == 0 || board[r][c-1] != 'X') && (c == 0 || board[r-1][c] != 'X'), c-1 may become -1 (when c is 0), and -1 is invalid index (similar for r). when you write (r == 0 || board[r-1][c] != 'X') && (c == 0 || board[r][c-1] != 'X'), you always check if r is 0 or not before you compute r-1 (similar for c), and it makes sure that r-1 will be equal or larger than 0 when you use it as index.


  • 1
    K

    how can you calculate the O(n) ? I think it's O(nm)


  • 0
    N

    @kirai m is the row length of board, n is the column length of board, so m*n equals total number 'n', so it's a O(n) solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.