Number of Ships in a Rectangle

Problem

On a 2D sea represented as a grid, some ships are hiding at integer coordinates. You can't see them directly — but you have a magic oracle:

Sea.hasShips(topRight, bottomLeft) — returns true if there's at least one ship anywhere inside the rectangle defined by those two corners (inclusive).

Given the top-right and bottom-left corners of a search area, count exactly how many ships are inside.

Rules:

• At most 10 ships in the rectangle
• At most 400 calls to hasShips
• At most one ship per integer point
• Coordinates range from 0 to 1000

Input: ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

(Ship at [5,5] is outside the [0,0]→[4,4] rectangle)

Intuition

What makes this problem unusual?

Most problems give you data and ask you to process it. This one is different — you can't see the data. You don't know where the ships are. All you can do is ask yes-or-no questions: "Is there at least one ship in this rectangle?"

It's like a guessing game. Imagine you're a coast guard with a radar that can only scan rectangular regions and tells you "yes, something's there" or "no, nothing." How do you count the exact number of ships?

The brute force idea (and why it fails)

The most obvious approach: check every single point individually.

for x from 0 to 1000:
  for y from 0 to 1000:
    if sea.hasShips([x, y], [x, y]):
      count++

A single point is just a 1×1 rectangle where topRight equals bottomLeft. If hasShips returns true, there's a ship there.

The problem? The grid is 1000×1000 = 1,000,000 points. We only get 400 calls. This approach needs 2,500× more calls than we're allowed.

A better idea: what if we could eliminate large empty areas?

Here's the insight. If we ask hasShips about a large rectangle and it says "no", we just ruled out thousands of points in one call. We don't need to check any of them individually.

hasShips([500, 500], [0, 0]) → false

One call just eliminated 250,000 points. That's powerful.

But if it says "yes", we know there's at least one ship somewhere in that area — we just don't know exactly where or how many. We need to narrow down further.

The divide and conquer strategy

This is where divide and conquer comes in. The idea:

1. Ask if the current rectangle has any ships
2. If no → stop, return 0 (prune this entire region)
3. If yes → split the rectangle into 4 smaller quadrants and search each one
4. Keep splitting until you reach a single point — if hasShips said yes, there's exactly 1 ship there

It's exactly like a quad-tree: at each step, we divide the 2D space into 4 quarters.

┌────────────┬────────────┐
│            │            │
│  top-left  │ top-right  │
│            │            │
├────────────┼────────────┤
│            │            │
│ bottom-left│bottom-right│
│            │            │
└────────────┴────────────┘

Let's see this in action

Suppose our sea looks like this (ships marked with *):

y
4 │ . . . * .
3 │ . . * . .
2 │ . * . . .
1 │ * . . . .
0 │ . . . . .
  └──────────
    0 1 2 3 4   x

Ships at (1,1), (2,2), (3,3). We want to count them.

Step 1: Ask about the whole region [0,0]→[4,4]

hasShips([4,4], [0,0]) → true (ships exist!)

Split at midpoint (2, 2) into 4 quadrants:

y
4 │ . . ║ . * .
3 │ . . ║ * . .
  ║═════╬═══════
2 │ . * ║ . . .
1 │ * . ║ . . .
0 │ . . ║ . . .
  └──────────────
    0 1  2  3 4   x

The four quadrants are:

• Bottom-left: [0,0]→[2,2]
• Bottom-right: [3,0]→[4,2]
• Top-left: [0,3]→[2,4]
• Top-right: [3,3]→[4,4]

Step 2: Ask about each quadrant

hasShips([2,2], [0,0]) → true   (ships at (1,1) and (2,2))
hasShips([4,2], [3,0]) → false  (no ships! prune ✂️)
hasShips([2,4], [0,3]) → false  (no ships! prune ✂️)
hasShips([4,4], [3,3]) → true   (ship at (3,3))

Two quadrants pruned immediately — we'll never look inside them again. Two quadrants need further splitting.

Step 3: Keep splitting the "true" quadrants until we reach individual points.

Bottom-left [0,0]→[2,2] splits into 4, which eventually finds ships at (1,1) and (2,2).

Top-right [3,3]→[4,4] splits and finds the ship at (3,3).

Result: 3 ✓

Why does pruning save so many calls?

Without pruning, we'd split every rectangle all the way down to individual points. A 1000×1000 grid has depth log2(1000) ≈ 10, and 4 children per node would be 4^10 ≈ 1,000,000 nodes.

But with pruning, we only continue splitting where ships actually exist. Since there are at most 10 ships, the recursion only goes deep along paths leading to ships. Most of the tree gets pruned at the first or second level.

Let's count the calls carefully

Why does the 400 limit work?

Think of it this way. Each ship sits at the bottom of a path from the root down to a single point. That path has depth log2(1000) ≈ 10. At each level, we call hasShips once. So each ship costs about 10 calls to pin down.

But at each level, a "true" answer spawns 4 children, each making a call. If we're unlucky and all 4 children say "true" at every level for all ships... the math works out to at most 4 × 10 × 10 = 400 calls.

Here's the breakdown:

• 10 ships maximum
• 10 levels of recursion (depth of quad-tree on a 1000×1000 grid)
• 4 calls per split (one per quadrant)
• But most quadrants are empty and get pruned

The worst case is tight against the 400-call limit — the constraint was designed for this exact algorithm.

How to split the rectangle

We find the midpoint of the x-range and y-range:

midX = floor((bottomLeft.x + topRight.x) / 2)
midY = floor((bottomLeft.y + topRight.y) / 2)

Then the four quadrants are:

Bottom-left:  [bx, by]      → [midX, midY]
Bottom-right: [midX+1, by]  → [tx, midY]
Top-left:     [bx, midY+1]  → [midX, ty]
Top-right:    [midX+1, midY+1] → [tx, ty]

Notice the +1 offsets — this ensures no overlap between quadrants. Every point belongs to exactly one quadrant.

        midX  midX+1
          ↓     ↓
    ┌─────┬─────┐
    │ TL  │ TR  │ ← midY+1 to ty
    ├─────┼─────┤
    │ BL  │ BR  │ ← by to midY
    └─────┴─────┘

What's the base case?

The recursion stops in two situations:

1. hasShips returns false → No ships here, return 0
2. We've narrowed down to a single point (bx === tx && by === ty) → We already know hasShips is true (otherwise we'd have returned 0 above), so there's exactly 1 ship here, return 1

What about invalid rectangles?

After splitting, it's possible to create an invalid rectangle where bx > tx or by > ty. This happens when the rectangle is too small to split evenly. For example, a 1-wide rectangle split horizontally gives one normal quadrant and one where bx > tx. We handle this with an early return:

if (bx > tx || by > ty) return 0;

Solution

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * function Sea() {
 *     @param {integer[]} topRight
 *     @param {integer[]} bottomLeft
 *     @return {boolean}
 *     this.hasShips = function(topRight, bottomLeft) {
 *         ...
 *     };
 * };
 */
 
function countShips(sea, topRight, bottomLeft) {
  const [tx, ty] = topRight;
  const [bx, by] = bottomLeft;
 
  // Invalid rectangle (can happen after splitting)
  if (bx > tx || by > ty) return 0;
 
  // No ships in this region — prune the entire subtree
  if (!sea.hasShips(topRight, bottomLeft)) return 0;
 
  // Single point, and we know hasShips was true — exactly 1 ship
  if (bx === tx && by === ty) return 1;
 
  // Split into 4 quadrants
  const midX = Math.floor((bx + tx) / 2);
  const midY = Math.floor((by + ty) / 2);
 
  return (
    countShips(sea, [midX, midY], [bx, by]) +             // bottom-left
    countShips(sea, [tx, midY], [midX + 1, by]) +          // bottom-right
    countShips(sea, [midX, ty], [bx, midY + 1]) +          // top-left
    countShips(sea, [tx, ty], [midX + 1, midY + 1])        // top-right
  );
}

Line-by-line breakdown

Lines 2-3 — Destructure the corners into named variables. t for top-right, b for bottom-left.

Line 5-6 — Guard against invalid rectangles. After splitting, one of the quadrants might have flipped coordinates (left > right). Return 0 immediately.

Line 8-9 — The pruning step. This is the most important line. One call to hasShips can eliminate an entire region — potentially hundreds of thousands of points. If no ships are here, don't recurse.

Line 11-12 — Base case. We've zoomed in to a single point. Since we passed the hasShips check above (it returned true), there must be exactly one ship at this point.

Lines 14-15 — Compute midpoints to split the rectangle into 4 equal-ish quadrants. Math.floor rounds down, so the bottom-left quadrant gets the extra row/column when dimensions are odd.

Lines 17-22 — Recurse into all 4 quadrants and sum their ship counts. The +1 offsets prevent overlap between quadrants.

Walking through the example

ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]

Note: [5,5] is outside our search rectangle, so it won't be found.

countShips([4,4], [0,0])
│ hasShips → true
│ midX=2, midY=2
│
├── countShips([2,2], [0,0])     ← bottom-left
│   │ hasShips → true (ships at (1,1) and (2,2))
│   │ midX=1, midY=1
│   │
│   ├── countShips([1,1], [0,0])     ← BL of BL
│   │   │ hasShips → true
│   │   │ midX=0, midY=0
│   │   │
│   │   ├── countShips([0,0], [0,0]) → hasShips false → 0
│   │   ├── countShips([1,0], [1,0]) → hasShips false → 0
│   │   ├── countShips([0,1], [0,1]) → hasShips false → 0
│   │   └── countShips([1,1], [1,1]) → hasShips true, single point → 1 ✓ ship!
│   │   = 1
│   │
│   ├── countShips([2,1], [2,0])     ← BR of BL
│   │   hasShips → false → 0 (pruned!)
│   │
│   ├── countShips([1,2], [0,2])     ← TL of BL
│   │   hasShips → false → 0 (pruned!)
│   │
│   └── countShips([2,2], [2,2])     ← TR of BL
│       hasShips → true, single point → 1 ✓ ship!
│   = 1 + 0 + 0 + 1 = 2
│
├── countShips([4,2], [3,0])     ← bottom-right
│   hasShips → false → 0 (pruned!)
│
├── countShips([2,4], [0,3])     ← top-left
│   hasShips → false → 0 (pruned!)
│
└── countShips([4,4], [3,3])     ← top-right
    │ hasShips → true (ship at (3,3))
    │ midX=3, midY=3
    │
    ├── countShips([3,3], [3,3]) → hasShips true, single point → 1 ✓ ship!
    ├── countShips([4,3], [4,3]) → hasShips false → 0
    ├── countShips([3,4], [3,4]) → hasShips false → 0
    └── countShips([4,4], [4,4]) → hasShips false → 0
    = 1

Total: 2 + 0 + 0 + 1 = 3 ✓

Let's count our hasShips calls: 1 (root) + 4 (level 1) + 4 (BL splits) + 4 (BL-BL splits) + 4 (TR splits) = 17 calls to find 3 ships in a 5×5 grid. The brute force would need 25 calls — and on the full 1000×1000 grid, the savings are enormous.

Why quad-tree and not binary search?

You might wonder: why split into 4 parts instead of 2? We're working in 2D, so splitting along one axis only halves the problem. Splitting along both axes quarters it.

You could do binary splits (e.g., split vertically, then horizontally), and it would still work. But the quad-tree approach is the natural 2D extension of binary search, and it matches the 400-call budget perfectly.

1D problem → binary search (split into 2)
2D problem → quad-tree (split into 4)
3D problem → octree (split into 8)

Visualizing the pruning

Let's see why this is so efficient. On a 1000×1000 grid with 3 ships:

Level 0: 1 rectangle    → 1 call  → 1 says "true"
Level 1: 4 rectangles   → 4 calls → maybe 2 say "true", 2 pruned
Level 2: 8 rectangles   → 8 calls → maybe 3 say "true", 5 pruned
Level 3: 12 rectangles  → 12 calls → maybe 3 say "true", 9 pruned
...
Level 10: reach individual points → 3 say "true" (the ships!)

At every level, most branches die immediately. Only the branches containing ships survive. The tree is extremely sparse — like a bush with only a few long branches reaching the ground, not a full tree.

An analogy: finding people in a building

Imagine you're looking for people in a giant 1000-floor building with 1000 rooms per floor. You have a magic sensor that tells you "is anyone in this section of the building?"

Brute force: Check every single room. 1,000,000 checks.

Divide and conquer:

1. Split the building into 4 sections. Check each.
2. "Anyone in the north-east quarter?" → "No." Skip 250,000 rooms.
3. "Anyone in the south-west quarter?" → "Yes." Split that quarter into 4...
4. Keep narrowing down until you find the exact rooms with people.

If there are only 10 people in a million rooms, you find them all in a few hundred checks.

Complexity

• Time: O(S × log(max(M, N))) — where S is the number of ships (≤ 10) and M×N is the grid size. Each ship requires ~log(1000) ≈ 10 levels of recursion to pinpoint.
• Space: O(log(max(M, N))) — the recursion stack depth. At most ~10 frames deep.
• API calls: At most 400, guaranteed by the constraints and the algorithm design.

Common mistakes

1. Forgetting the invalid rectangle check — After splitting, midX + 1 might exceed tx for narrow rectangles. Without the bx > tx || by > ty guard, you'll recurse forever or get wrong answers.

2. Overlapping quadrants — If you forget the +1 offsets (e.g., writing [midX, by] instead of [midX + 1, by] for the bottom-right), points on the boundary get counted in multiple quadrants, giving inflated results.

3. Splitting on only one axis — If you only split horizontally or vertically, you'll make too many calls. Splitting both axes simultaneously is what keeps us within 400 calls.

4. Not pruning before splitting — The hasShips check MUST come before the split. If you split first and then check each quadrant, you're doing 4× the work at every level.

Key Takeaway

When you have a sparse search space (few ships in a huge grid) and can only ask yes/no questions about regions, divide and conquer with pruning is the key pattern. The quad-tree approach — split the space into 4, immediately abandon empty regions, recurse into non-empty ones — turns a million-point search into a few hundred targeted queries. The pruning does the heavy lifting: one "no" answer eliminates an entire subtree of future work.