Number of Ships in a Rectangle Python Solution

Tested Python solution for LeetCode 1274 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 1274, Hard. Topics: Array, Divide and Conquer, Interactive. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1274   # by problem number
lcpy gen -s number_of_ships_in_a_rectangle   # by problem name

​

Problem

(This problem is an interactive problem.)

Each ship is located at an integer point on the sea represented by a cartesian plane, and each integer point may contain at most 1 ship.

You have a function Sea.has_ships(top_right, bottom_left) which takes two points as arguments and returns true if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points: the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to has_ships will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will be disqualified.

The API is:

class Sea:
    def has_ships(self, top_right: 'Point', bottom_left: 'Point') -> bool: ...

class Point:
    def __init__(self, x: int, y: int) -> None:
        self.x = x
        self.y = y

​

Examples

Input:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Input:
ships = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,0]
Output: 3

​

Constraints

• On the input ships is only given to initialize the map internally. You must solve this problem “blindfolded”. In other words, you must find the answer using the given has_ships API, without knowing the ships position.
• 0 <= bottomLeft[0] <= topRight[0] <= 1000
• 0 <= bottomLeft[1] <= topRight[1] <= 1000
• topRight != bottomLeft

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Point:
    # Test-harness value type for a cartesian point on the sea
    def __init__(self, x: int, y: int) -> None:
        self.x = x
        self.y = y


class Sea:
    # Test-harness API: backs the interactive has_ships query with the ships
    def __init__(self, ships: list[list[int]]) -> None:
        self.ships = {(x, y) for x, y in ships}
        self.calls = 0

    def has_ships(self, top_right: Point, bottom_left: Point) -> bool:
        self.calls += 1
        if self.calls > 400:
            msg = "has_ships exceeded the 400-call judge limit"
            raise RuntimeError(msg)
        return any(
            bottom_left.x <= x <= top_right.x and bottom_left.y <= y <= top_right.y
            for x, y in self.ships
        )


class Solution:
    # Time: O(C * log(max(m, n))) API calls, C = ships inside the rectangle
    # Space: O(log(max(m, n))) recursion
    def count_ships(self, sea: Sea, top_right: Point, bottom_left: Point) -> int:
        def dfs(tr: Point, bl: Point) -> int:
            x1, y1 = bl.x, bl.y
            x2, y2 = tr.x, tr.y
            if x1 > x2 or y1 > y2:
                return 0
            if not sea.has_ships(tr, bl):
                return 0
            if x1 == x2 and y1 == y2:
                return 1
            midx = (x1 + x2) // 2
            midy = (y1 + y2) // 2
            return (
                dfs(tr, Point(midx + 1, midy + 1))
                + dfs(Point(midx, y2), Point(x1, midy + 1))
                + dfs(Point(midx, midy), bl)
                + dfs(Point(x2, midy), Point(midx + 1, y1))
            )

        return dfs(top_right, bottom_left)

​

Complexity

Time	Space
O(C * log(max(m, n))) API calls, C = ships inside the rectangle	O(log(max(m, n))) recursion

​

Tags

NeetCode All.