Skip to main content
Talentd

Number of Ships in a Rectangle - Solution & Explanation

HardPremiumFree on FleetCodeArrayDivide and ConquerInteractive10 min readAsked at: Applied Intuition, Bloomberg
Practice this problem

Problem Statement

(This problem is an interactive problem.)

Each ship is located at an integer point on the sea represented by a cartesian plane, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true If there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points: the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

 

Example :

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Example 2:

Input: ans = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,0]
Output: 3

 

Constraints:

  • On the input ships is only given to initialize the map internally. You must solve this problem "blindfolded". In other words, you must find the answer using the given hasShips API, without knowing the ships position.
  • 0 <= bottomLeft[0] <= topRight[0] <= 1000
  • 0 <= bottomLeft[1] <= topRight[1] <= 1000
  • topRight != bottomLeft

Approach Overview

Problem Overview: You are given an interactive API Sea.hasShips(topRight, bottomLeft) that returns whether at least one ship exists inside a rectangle. The grid is hidden, and you must count the exact number of ships within a given rectangle while minimizing API calls.

The key constraint: you cannot directly inspect grid cells. The only operation available is querying whether a region contains at least one ship. Because of that limitation, the solution relies heavily on divide and conquer to recursively split the search space.

Approach 1: Brute Force Grid Scan (O(N × M) time, O(1) space)

The naive idea is to check every coordinate inside the rectangle and determine if a ship exists there. In a normal grid problem, you would iterate through all cells using nested loops and count ships directly. However, the API does not allow checking individual cells unless you form a rectangle query for each coordinate.

This leads to a large number of API calls. For a rectangle of size N × M, the algorithm would issue up to N × M queries. Because interactive problems often restrict the number of API calls, this approach quickly becomes impractical. It also ignores the valuable pruning information returned by hasShips.

Approach 2: Recursion + Divide and Conquer (O(S log A) time, O(log A) space)

The optimal strategy recursively splits the rectangle into smaller regions. Start by calling hasShips(topRight, bottomLeft). If the API returns false, the region contains zero ships and you immediately stop exploring that branch. This pruning step prevents unnecessary work.

If the API returns true and the rectangle represents a single point (x1 == x2 and y1 == y2), you found exactly one ship. Otherwise, divide the rectangle into four quadrants using the midpoint and recursively search each sub-rectangle. This approach behaves like a quadtree search.

The efficiency comes from the fact that recursion only expands regions that actually contain ships. If the maximum number of ships is S, the algorithm performs roughly O(S log A) API calls where A is the area of the search space. The recursion depth is logarithmic because the rectangle keeps shrinking.

This technique is a classic example of divide and conquer combined with pruning in an interactive problem. Instead of scanning the entire array-like grid, the algorithm quickly eliminates empty regions.

Recommended for interviews: Recursion with divide and conquer is the expected solution. Interviewers want to see that you use the API result to prune large empty regions instead of checking every coordinate. Demonstrating the brute-force idea first shows baseline understanding, but implementing the recursive quadrant split proves you can optimize API-bound problems.

Solution

Since there are at most 10 ships in the rectangle, we can divide the rectangle into four sub-rectangles, calculate the number of ships in each sub-rectangle, and then add the number of ships in the four sub-rectangles. If there are no ships in a sub-rectangle, then there is no need to continue dividing.

The time complexity is O(C times log max(m, n)), and the space complexity is O(log max(m, n)). Where C is the number of ships, and m and n are the length and width of the rectangle, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Coordinate ScanO(N × M)O(1)Conceptual baseline when direct grid access is available
Recursion + Divide and Conquer (Quadrant Split)O(S log A)O(log A)Interactive API problems where empty regions can be pruned efficiently

Video Solution

5136 Number of Ships in a Rectangle (Biweekly Contest 14) • Kelvin Chandra • 2,056 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Number of Ships in a Rectangle easy or hard?
LeetCode classifies this problem as Hard because it requires designing an efficient divide and conquer strategy under API constraints. The challenge is minimizing API calls while still counting every ship accurately.
Number of Ships in a Rectangle Python/Java solution
Implement a recursive function that accepts the rectangle boundaries. Call hasShips to check if the region contains ships. If the region is a single point, return 1; otherwise split the rectangle into four parts and sum the results. The same logic works in Python, Java, C++, Go, and TypeScript.
How to solve Number of Ships in a Rectangle in O(S log N)?
Start with the full rectangle and call the hasShips API. If ships exist and the rectangle is larger than one cell, split it into four quadrants using the midpoint and recursively explore each quadrant. Because only ship-containing regions expand, the total number of recursive calls grows roughly proportional to S times the logarithmic depth of the grid.
What is the best approach for Number of Ships in a Rectangle?
The optimal solution uses recursion with divide and conquer. You query the API to check whether a rectangle contains any ships, and if it does, split the region into four smaller rectangles. Empty regions are pruned immediately, which dramatically reduces API calls.
Is Number of Ships in a Rectangle asked at Google/Amazon/Meta?
Divide and conquer grid search problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The interactive constraint tests whether candidates can minimize expensive API calls while designing recursive search strategies.
What data structure is used in Number of Ships in a Rectangle?
The solution mainly relies on recursion and a conceptual quadtree-style space partitioning. Instead of storing the entire grid, the algorithm dynamically splits rectangles and uses the API result to decide whether to continue searching.
What is the time complexity of Number of Ships in a Rectangle?
The divide and conquer approach runs in approximately O(S log A) time, where S is the number of ships and A is the area of the search region. The algorithm only expands rectangles that contain ships, so empty regions are skipped after a single API query.

Ready to solve this problem?

Practice Number of Ships in a Rectangle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays