Leetcode 1274. Number of Ships in a Rectangle
Given a black-box API hasShips(topRight, bottomLeft) that returns whether at least one ship (point at integer coordinates) lies inside an axis-aligned rectangle, compute the exact number of ships in a target rectangle by recursively subdividing the region (quadtree/divide-and-conquer), pruning empty subrectangles and stopping when a region reduces to a single point.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late September, 2026
LeetCode 1274, "Number of Ships in a Rectangle," is an interactive problem where you count ships on a 2D plane using a hasShips(topRight, bottomLeft) API without knowing their exact coordinates. Problem Overview • Goal: Count the total number of ships in a given rectangular area. • Input: The topRight and bottomLeft coordinates of the rectangle. • API: sea.hasShips(topRight, bottomLeft) returns true if there is at least one ship in that rectangle, and false otherwise. • Constraints: At most 10 ships exist total; max 400 API calls allowed. Approach: Divide and Conquer The most efficient way to solve this is using a divide-and-conquer (recursive quadtree-like) strategy: 1. Base Case 1: If the rectangle is invalid (e.g., topRight < bottomLeft), return 0. 2. Base Case 2: If hasShips returns false for the current rectangle, return 0 (prune empty regions). 3. Base Case 3: If the top-right and bottom-left coordinates are the exact same point (topRight == bottomLeft) and hasShips is true, you found a ship, so return 1. 4. Recursive Step: Split the rectangle into four smaller quadrants by finding the middle point (midX, midY): • Bottom-Left quadrant • Bottom-Right quadrant • Top-Left quadrant • Top-Right quadrant 5. Recursively call the counting function on each quadrant and sum the results
Hello Interview Premium
Your account is free and you can post anonymously if you choose.