Skip to content

1274. Number of Ships in a Rectangle 👍

  • Time: $O(\log mn)$
  • Space: $O(\log mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *  public:
 *   bool hasShips(vector<int> topRight, vector<int> bottomLeft);
 * };
 */

class Solution {
 public:
  int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
    if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1])
      return 0;
    if (!sea.hasShips(topRight, bottomLeft))
      return 0;

    // sea.hashShips(topRight, bottomLeft) == true
    if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
      return 1;

    const int mx = (topRight[0] + bottomLeft[0]) / 2;
    const int my = (topRight[1] + bottomLeft[1]) / 2;
    int ans = 0;
    // the top-right
    ans += countShips(sea, topRight, {mx + 1, my + 1});
    // the bottom-right
    ans += countShips(sea, {topRight[0], my}, {mx + 1, bottomLeft[1]});
    // the top-left
    ans += countShips(sea, {mx, topRight[1]}, {bottomLeft[0], my + 1});
    // the bottom-left
    ans += countShips(sea, {mx, my}, bottomLeft);
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *   public boolean hasShips(int[] topRight, int[] bottomLeft);
 * }
 */

class Solution {
  public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
    if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1])
      return 0;
    if (!sea.hasShips(topRight, bottomLeft))
      return 0;

    // sea.hashShips(topRight, bottomLeft) == true
    if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
      return 1;

    final int mx = (topRight[0] + bottomLeft[0]) / 2;
    final int my = (topRight[1] + bottomLeft[1]) / 2;
    int ans = 0;
    // the top-right
    ans += countShips(sea, topRight, new int[] {mx + 1, my + 1});
    // the bottom-right
    ans += countShips(sea, new int[] {topRight[0], my}, new int[] {mx + 1, bottomLeft[1]});
    // the top-left
    ans += countShips(sea, new int[] {mx, topRight[1]}, new int[] {bottomLeft[0], my + 1});
    // the bottom-left
    ans += countShips(sea, new int[] {mx, my}, bottomLeft);
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Sea(object):
#   def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
#     pass
#
# class Point(object):
# def __init__(self, x: int, y: int):
# self.x = x
# self.y = y

class Solution(object):
  def countShips(
      self,
      sea: 'Sea',
      topRight: 'Point',
      bottomLeft: 'Point',
  ) -> int:
    if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y:
      return 0
    if not sea.hasShips(topRight, bottomLeft):
      return 0

    # sea.hashShips(topRight, bottomLeft) == True
    if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
      return 1

    mx = (topRight.x + bottomLeft.x) // 2
    my = (topRight.y + bottomLeft.y) // 2
    ans = 0
    # the top-right
    ans += self.countShips(sea, topRight, Point(mx + 1, my + 1))
    # the bottom-right
    ans += self.countShips(sea, Point(topRight.x, my),
                           Point(mx + 1, bottomLeft.y))
    # the top-left
    ans += self.countShips(sea, Point(mx, topRight.y),
                           Point(bottomLeft.x, my + 1))
    # the bottom-left
    ans += self.countShips(sea, Point(mx, my), bottomLeft)
    return ans