[
interactive
2d-array
binary search
]
Leetcode 1274 Number of Ships in a Rectangle
Problem statement
https://leetcode.com/problems/number-of-ships-in-a-rectangle/
Solution
It is intercative problem, where we need to decide strategy depending on result. Let us on each step separate searching area into 4
rectangles and recursively ask the same question. Each time we reduce size by 2
, so distance from root to leaves to recursion is no more than log(max(M, N)) <= 10
. To reach one leaf we need to make no more than 4*10
calls, because we have 10
levels and 4
calls on each level, so in total we will make no more than 4*10*10 = 400
calls to find all <= 10
leaves.
Complexity
We need to make log(max(M, N)) * leaves * 4
calls of function.
Code
class Solution:
def countShips(self, sea, topRight, bottomLeft):
x1, y1 = bottomLeft.x, bottomLeft.y
x2, y2 = topRight.x, topRight.y
if x1 > x2 or y1 > y2 or not sea.hasShips(topRight, bottomLeft): return 0
if x1 == x2 and y1 == y2: return 1
xm, ym = (x1 + x2)//2, (y1 + y2)//2
cands = [(xm, ym, x1, y1), (xm, y2, x1, ym+1), (x2, ym, xm+1, y1), (x2, y2, xm+1, ym+1)]
return sum(self.countShips(sea, Point(a, b), Point(c, d)) for a, b, c, d in cands)