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)