Number of Ships in a Rectangle - Solution & Explanation

Problem Overview: You are given an interactive API Sea.hasShips(topRight, bottomLeft) that returns whether at least one ship exists inside a rectangle. The grid is hidden, and you must count the exact number of ships within a given rectangle while minimizing API calls.

The key constraint: you cannot directly inspect grid cells. The only operation available is querying whether a region contains at least one ship. Because of that limitation, the solution relies heavily on divide and conquer to recursively split the search space.

Approach 1: Brute Force Grid Scan (O(N × M) time, O(1) space)

The naive idea is to check every coordinate inside the rectangle and determine if a ship exists there. In a normal grid problem, you would iterate through all cells using nested loops and count ships directly. However, the API does not allow checking individual cells unless you form a rectangle query for each coordinate.

This leads to a large number of API calls. For a rectangle of size N × M, the algorithm would issue up to N × M queries. Because interactive problems often restrict the number of API calls, this approach quickly becomes impractical. It also ignores the valuable pruning information returned by hasShips.

Approach 2: Recursion + Divide and Conquer (O(S log A) time, O(log A) space)

The optimal strategy recursively splits the rectangle into smaller regions. Start by calling hasShips(topRight, bottomLeft). If the API returns false, the region contains zero ships and you immediately stop exploring that branch. This pruning step prevents unnecessary work.

If the API returns true and the rectangle represents a single point (x1 == x2 and y1 == y2), you found exactly one ship. Otherwise, divide the rectangle into four quadrants using the midpoint and recursively search each sub-rectangle. This approach behaves like a quadtree search.

The efficiency comes from the fact that recursion only expands regions that actually contain ships. If the maximum number of ships is S, the algorithm performs roughly O(S log A) API calls where A is the area of the search space. The recursion depth is logarithmic because the rectangle keeps shrinking.

This technique is a classic example of divide and conquer combined with pruning in an interactive problem. Instead of scanning the entire array-like grid, the algorithm quickly eliminates empty regions.

Recommended for interviews: Recursion with divide and conquer is the expected solution. Interviewers want to see that you use the API result to prune large empty regions instead of checking every coordinate. Demonstrating the brute-force idea first shows baseline understanding, but implementing the recursive quadrant split proves you can optimize API-bound problems.