LeetCode 419: Battleships in a Board Solution
Master LeetCode problem 419 (Battleships in a Board), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
419. Battleships in a Board
Problem Explanation
Explanation
To solve this problem efficiently, we can iterate through the board and count the number of battleships by checking if the current cell is a 'X' and if its left and top neighbors are not 'X'. This ensures that we are counting only the starting cells of battleships.
We will iterate through the board once and increment the count whenever we find a battleship's starting cell. At the end of the iteration, the count will represent the total number of battleships on the board.
- Time complexity: O(m*n) where m and n are the dimensions of the board
- Space complexity: O(1)
Solution Code
class Solution {
public int countBattleships(char[][] board) {
int count = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X')) {
count++;
}
}
}
return count;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 419 (Battleships in a Board)?
This page provides optimized solutions for LeetCode problem 419 (Battleships in a Board) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 419 (Battleships in a Board)?
The time complexity for LeetCode 419 (Battleships in a Board) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 419 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 419 in Java, C++, or Python.