Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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])
  }
}