O(n) Java solution (2 ms)


  • 1
    A

    My logic was this:

    Iterate through the grid. If the cell isn't an X, ignore it. If it is an X, check to see if the one below it is an X. If it is, ignore this one (we will add one to our sum when we reach the bottom X in the vertical ship). If there isn't an X below it, that means it's a horizontal ship, so we'll increment the sum and skip to the next non-X. Special care is taken for the last row. I ended up combining most of the logic for both cases.

    	public int countBattleships(char[][] board) {
                if (board.length == 0) return 0;
    	    int sum = 0;
    	    int rows = board.length;
    	    int cols = board[0].length;
    	    
    	    for (int r = 0; r < rows; r++) {
    	    	for (int c = 0; c < cols; c++) {
    	    	    if(board[r][c] != 'X') continue;
    	    	    if (r == rows - 1 || board[r+1][c] != 'X') {
    	   	        sum++;
    			if(r < rows-1 || !(rows > 1 && board[r-1][c] == 'X')) {
    			    while(c < cols && board[r][c] == 'X') {
    				c++;
    	                    }
    			}
                        }
    		}
    	    }
    	    return sum;
    	}
    

  • 1
    A

    Why is this O(n)? It still iterates all the elements in matrix. Shouldn't this be O(mn)?


  • 0
    A

    @adrianhihi Yes, but typically we say O(n) where n is the number of elements in the input. In this problem we're also saying "n" to mean the number of rows. If we use n to mean the number of rows, O(mn) is more accurate - but I was using it as "n = number of cells in the matrix"


  • 0
    A

    @Alderdragon I see. Thanks for your clarification. Great answer!


Log in to reply
 

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