#1274
Hard Algorithms Number of ships in a rectangle
Array Divide and Conquer Interactive
68.9% acceptance
Mar 31, 2026
536
70
No description available.
Solution
Rust
Time O(2^n)
Space O(n)
impl Solution {
pub fn count_ships(sea: &Sea, top_right: Vec<i32>, bottom_left: Vec<i32>) -> i32 {
if bottom_left[0] > top_right[0] || bottom_left[1] > top_right[1] {
return 0;
}
if !sea.hasShips(top_right.clone(), bottom_left.clone()) {
return 0;
}
if top_right[0] == bottom_left[0] && top_right[1] == bottom_left[1] {
return 1;
}
let mid_x = (top_right[0] + bottom_left[0]) / 2;
let mid_y = (top_right[1] + bottom_left[1]) / 2;
// Split into 4 quadrants
Self::count_ships(sea, vec![mid_x, mid_y], bottom_left.clone())
+ Self::count_ships(sea, vec![top_right[0], mid_y], vec![mid_x + 1, bottom_left[1]])
+ Self::count_ships(sea, vec![mid_x, top_right[1]], vec![bottom_left[0], mid_y + 1])
+ Self::count_ships(sea, top_right.clone(), vec![mid_x + 1, mid_y + 1])
}
}