Battleships in a Board
Updated
Problem statement
A battleship board is given as m strings of length n. board[r][c] is 'X' when the cell in row r, column c is part of a ship, and '.' when it is water.
Every ship is a straight line of one or more cells: it either lies along one row (1 x k) or stands in one column (k x 1). Two different ships never share a side, so at least one water cell separates them horizontally and vertically. They may still meet diagonally, at a corner.
Return the number of ships on the board.
Function
countBattleships(board: String[]) → intExamples
Example 1
board = ["XX.X","...X","X..X","X..."]return = 3There are three ships: (0,0)-(0,1) lying across row 0, (0,3)-(2,3) standing in column 3, and (2,0)-(3,0) standing in column 0 (row, column, 0-based). Every pair of ships is separated by water.
Example 2
board = ["X.X",".X.","X.X"]return = 5Five one-cell ships. The middle ship touches the four corner ships only at corners, never along a side, so each is its own ship.
Constraints
m == board.length,n == board[i].length, and1 <= m, n <= 200- Every
board[i][j]is'X'or'.'. - Every ship is a straight line of cells in one row or one column, and two ships never share a side.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Query Whether an Island Size ExistsMeta · ONSITE INTERVIEWMeta interview questions
- Maximum Number of Fish in a GridGlobalization Partners · ONSITE INTERVIEW
- Max Area of IslandGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Max Area of IslandRoku · ONSITE INTERVIEWRoku interview questions
- Number of IslandsExpedia · ONSITE INTERVIEWExpedia interview questions
- Max Area of IslandBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Area of IslandSambaNova Systems · ONSITE INTERVIEWSambaNova Systems interview questions