Number of Ships in a Rectangle

Number of Ships in a Rectangle

What is this problem about?

The Number of Ships in a Rectangle problem presents an interactive problem. Ships are hidden at integer coordinates in a rectangle. You can call hasShips(topRight, bottomLeft) which returns true if at least one ship is in the sub-rectangle. Find the total number of ships with the minimum number of API calls. This hard interactive coding problem uses divide and conquer.

Why is this asked in interviews?

Bloomberg asks this because it requires designing an efficient search strategy using divide and conquer — splitting the search space in half each time a sub-rectangle contains ships. The array, divide and conquer, and interactive interview pattern is the core, and optimal API usage is the key challenge.

Algorithmic pattern used

Recursive divide and conquer. If hasShips(topRight, bottomLeft) returns false: no ships, return 0. If the rectangle is a single point and hasShips returns true: return 1. Otherwise, split the rectangle into 4 sub-rectangles (or 2 for 1D cases) and recursively count ships in each. Sum the results. The total API calls = O(S log(maxArea)) where S is the number of ships.

Example explanation

Rectangle [0,0] to [4,4]. hasShips returns true.

• Split into 4 quadrants: [0,0]→[2,2], [3,0]→[4,2], [0,3]→[2,4], [3,3]→[4,4].
• Query each quadrant. Only [0,0]→[2,2] returns true.
• Recurse: split [0,0]→[2,2] into 4. Find ship at [1,1] (single point, hasShips=true). Total ships = 1.

Common mistakes candidates make

• Linear scan (calling hasShips for each individual coordinate — O(area) calls, too many).
• Not handling the base case (single point) correctly.
• Splitting into 2 sub-rectangles instead of 4 (missing diagonal coverage).
• Not terminating when hasShips returns false for a sub-rectangle.

Interview preparation tip

Interactive divide-and-conquer problems require pruning based on the query result. If a sub-region has no ships (query returns false), don't recurse into it. This is analogous to binary search but in 2D. The key insight: split aggressively, prune aggressively. Each "false" answer eliminates an entire sub-rectangle without further API calls. Practice 2D divide and conquer on "find all objects in a rectangle" style problems.