NeetCode #173LC-1274HardArrays & Hashing
← Back to All Problems#173 · #1274 · Number of Ships in a Rectangle(矩形内船只的数目)
📌 Problem Statement & Constraints
This is an interactive problem. A
Sea object has a hasShips(topRight, bottomLeft) method returning whether any ship exists in the given axis-aligned rectangle (inclusive). Given the rectangle bounds, return the total number of ships. Constraints: 0 <= ships <= 10, coordinates are up to 1000 x 1000, and hasShips may be called at most 400 times.💡 Core Algorithmic Approaches
- This is a divide-and-conquer search: if a rectangle contains no ships, return 0 without recursing.
- If the rectangle is a single cell and contains a ship, return 1.
- Otherwise split the rectangle into four quadrants at the midpoint and recurse into each.
- The
hasShipspruning is what keeps the query count low: empty regions cost exactly one call and are never subdivided.
💻 Benchmark Python3 Implementation
class Solution:
def countShips(self, sea: "Sea", topRight: List[int], bottomLeft: List[int]) -> int:
x1, y1 = bottomLeft
x2, y2 = topRight
if x1 > x2 or y1 > y2:
return 0
if not sea.hasShips(topRight, bottomLeft): # prune empty regions
return 0
if x1 == x2 and y1 == y2:
return 1 # single cell with a ship
mx = (x1 + x2) // 2
my = (y1 + y2) // 2
# four quadrants
return (self.countShips(sea, [mx, my], [x1, y1])
+ self.countShips(sea, [mx, y2], [x1, my + 1])
+ self.countShips(sea, [x2, my], [mx + 1, y1])
+ self.countShips(sea, [x2, y2], [mx + 1, my + 1]))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(ships * log(max coordinate)) in practice: each quadrant that contains ships is subdivided, while empty quadrants are pruned in one call.
💾 Space Complexity
O(log(max coordinate)) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Splitting without the
hasShipsprune: the recursion would explore the entire grid, exceeding the query limit. - Getting the quadrant boundaries wrong: the split must be disjoint and cover the whole rectangle, hence
mx/mx + 1andmy/my + 1. - Forgetting the base case for a single cell: without it, the recursion would split a 1x1 rectangle forever.
- Using
hasShipson a rectangle with reversed corners: the arguments must be ordered as(topRight, bottomLeft).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.