⚡Flashcard Drill➔
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

  1. This is a divide-and-conquer search: if a rectangle contains no ships, return 0 without recursing.
  2. If the rectangle is a single cell and contains a ship, return 1.
  3. Otherwise split the rectangle into four quadrants at the midpoint and recurse into each.
  4. The hasShips pruning 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 hasShips prune: 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 + 1 and my/my + 1.
  • Forgetting the base case for a single cell: without it, the recursion would split a 1x1 rectangle forever.
  • Using hasShips on 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems