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.

Description Hints 3 Solution Video 4:07

1274. Number of Ships in a Rectangle

Hard68.7% acceptance2 companiesPremium elsewhere, free here

(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

Asked at 2 companies

Bloomberg Applied Intuition

Topics

Hints open one at a time

Hint 1

Use divide and conquer technique.

Hint 2

Divide the query rectangle into 4 rectangles.

Hint 3

Use recursion to continue with the rectangles that has ships only.

4:07

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,1],[2,2],[3,3],[5,5]]
[4,4]
[0,0]

Input

[[1,1],[2,2],[3,3]]
[1000,1000]
[0,0]

Your code is saved on this device.Solution