Number of Ships in a Rectangle

Updated on 26 June, 2025
Number of Ships in a Rectangle header image

Problem Statement

In this interactive problem, the challenge is to determine the number of ships located within a designated rectangular area on a Cartesian plane, where each integer point on the plane can host at most one ship. The primary tool at your disposal is a provided function Sea.hasShips(topRight, bottomLeft), which confirms whether there is at least one ship in the rectangle defined by its two corner points: topRight and bottomLeft.

The task is to accurately count the ships in the rectangle using the function, with the added condition that there cannot be more than 10 ships in any queried rectangle. Critical to the approach is the limitation that the function cannot be called more than 400 times per solution attempt. Attempting to bypass these restrictions programmatically will lead to disqualification.

Examples

Example 1

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 and Intuition

Given the constraints and nature of the problem, the solution approaches this as a classic search problem, specifically one that can be tackled effectively with a "divide and conquer" strategy. Here is how one could structure the steps:

  1. Using the Sea.hasShips Function:

    • Begin by querying the entire rectangle defined by topRight and bottomLeft using the Sea.hasShips function. If the function returns false, then there are no ships in the rectangle, and you can return 0.
    • If the function returns true, indicating that there is at least one ship in the rectangle, proceed to split the rectangle into smaller sections.
  2. Divide and Conquer Approach:

    • Find the midpoint of each dimension of the rectangle (x and y axes). This will allow the rectangle to be divided into four smaller rectangles.
    • Recursively apply the hasShips function to each of these smaller rectangles.
    • If a rectangle is found to contain no ships (hasShips returns false), no further subdivision or checks are needed for that section.
    • Continue subdividing until rectangles are sufficiently small or until further subdivision is not feasible given the query limits.
  3. Aggregation and Count Restriction:

    • As the recursive function returns, aggregate the counts from each quadrant.
    • Ensure that the number of API calls does not exceed 400 to avoid a wrong answer judgment.

The recursive division helps in narrowing down the areas to precisely locate ships without excessive querying, adhering to the constraints provided. The challenge lies in optimizing the query distribution to not only stay within the allowed number of calls but also cover the search space effectively. This approach also works well given the guarantee that no more than 10 ships will be within any given query rectangle, making deeper divisions of the space more fruitful as the recursion progresses.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    int shipCount(Sea ocean, vector<int> upperRight, vector<int> lowerLeft) {
        if (lowerLeft[0] > upperRight[0] || lowerLeft[1] > upperRight[1])
            return 0;
        if (!ocean.hasShips(upperRight, lowerLeft))
            return 0;

        if (upperRight[0] == lowerLeft[0] && upperRight[1] == lowerLeft[1])
            return 1;

        int centerX = (upperRight[0] + lowerLeft[0]) / 2;
        int centerY = (upperRight[1] + lowerLeft[1]) / 2;
        return shipCount(ocean, {centerX, centerY}, lowerLeft) +
               shipCount(ocean, upperRight, {centerX + 1, centerY + 1}) +
               shipCount(ocean, {centerX, upperRight[1]}, {lowerLeft[0], centerY + 1}) +
               shipCount(ocean, {upperRight[0], centerY}, {centerX + 1, lowerLeft[1]});
    }
};

This C++ solution involves a method called shipCount which calculates the number of ships located within a rectangular area in a grid representing the ocean. The function takes three parameters:

  • ocean: An object which provides a hasShips method that returns true if there are ships within a specified rectangle, described by two corner points.
  • upperRight: A vector of two integers representing the upper-right corner coordinate of the rectangle.
  • lowerLeft: A vector of two integers representing the lower-left corner coordinate of the rectangle.

The function follows a divide-and-conquer strategy, centered on recursion to simplify the problem into smaller subsets. Here's how it works:

  1. If the lowerLeft coordinate is greater than the upperRight coordinate in either dimension, return 0 as this represents an invalid rectangle.
  2. If the ocean.hasShips for the current rectangle indicates there are no ships, return 0.
  3. Check if the rectangle has been reduced to a single point by comparing lowerLeft and upperRight. If they are the same, check if there's a ship at this point using ocean.hasShips, return 1 if a ship is present, otherwise, return 0.
  4. Calculate central dividing points, centerX and centerY, to divide the original rectangle into four smaller rectangles.
  5. Recursively compute the count of ships present in these four subdivided rectangles and sum up all the counts.

This approach ensures the problem is handled efficiently, especially suitable for large scale grids, as it narrows down the target areas recursively, reducing the calls to the potentially expensive hasShips method.

java
class Solution {
    public int shipCounter(Sea ocean, int[] topRight, int[] bottomLeft) {
        if (bottomLeft[0] > topRight[0] || bottomLeft[1] > topRight[1])
            return 0;
        if (!ocean.hasShips(topRight, bottomLeft))
            return 0;

        if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
            return 1;

        int midX = (topRight[0] + bottomLeft[0]) / 2;
        int midY = (topRight[1] + bottomLeft[1]) / 2;
        return shipCounter(ocean, new int[]{midX, midY}, bottomLeft) +
               shipCounter(ocean, topRight, new int[]{midX + 1, midY + 1}) +
               shipCounter(ocean, new int[]{midX, topRight[1]}, new int[]{bottomLeft[0], midY + 1}) +
               shipCounter(ocean, new int[]{topRight[0], midY}, new int[]{midX + 1, bottomLeft[1]});
    }
}

The Java solution provided counts the number of ships present in a rectangular area of the sea using a recursive approach. The method shipCounter utilizes a divide-and-conquer algorithm to efficiently detect and count ships within the given rectangle defined by its top-right and bottom-left corners.

  • The method first checks whether the corners of the current rectangle are valid; if the bottom-left corner is above or to the right of the top-right corner, or if there are no ships detected in the current rectangle (ocean.hasShips returns false), it returns 0.
  • If the rectangle reduces to a single point (the coordinates of the bottom-left and the top-right corners match), and if there is a ship at this point, the method returns 1.
  • For larger rectangles, the method divides the rectangle into four quadrants by calculating the mid-points (midX, midY).
  • The method then recursively counts ships in these quadrants by calling shipCounter for each quadrant with updated boundaries.

This algorithm is a practical example of how recursive functions coupled with divide-and-conquer strategy can be used to solve complex problems by breaking them down into simpler sub-problems that are easier to manage and solve. This approach ensures that the area being checked for ships is minimized at every recursive step, improving the efficiency of the ship detection process.

python
class Solution:
    def shipCount(self, ocean: 'Sea', upperRight: 'Point', lowerLeft: 'Point') -> int:
        if (lowerLeft.x > upperRight.x) or (lowerLeft.y > upperRight.y):
            return 0
        if not ocean.hasShips(upperRight, lowerLeft):
            return 0

        if (upperRight.x == lowerLeft.x) and (upperRight.y == lowerLeft.y):
            return 1

        midX = (upperRight.x + lowerLeft.x) // 2
        midY = (upperRight.y + lowerLeft.y) // 2
        return self.shipCount(ocean, Point(midX, midY), lowerLeft) + \
               self.shipCount(ocean, upperRight, Point(midX + 1, midY + 1)) + \
               self.shipCount(ocean, Point(midX, upperRight.y), Point(lowerLeft.x, midY + 1)) + \
               self.shipCount(ocean, Point(upperRight.x, midY), Point(midX + 1, lowerLeft.y))

The solution provided is a Python function focused on calculating the number of ships located within a defined rectangular area in a sea, represented by given coordinates. This approach uses a divide and conquer strategy, specifically adapted for quadrants separation. Here is a concise breakdown of the strategy:

  1. Base Cases:

    • If the bottom-left point lowerLeft of the rectangle is above or to the right of the top-right point upperRight, the function returns 0, implying no rectangle exists under the provided definition.
    • Check whether the rectangle contains any ships using the ocean.hasShips() method. If the rectangle does not contain any ships, return 0.
    • If both the coordinates of lowerLeft and upperRight are identical, it means the area is reduced to a single point, and if it contains a ship, return 1.
  2. Recursion for Subdivision:

    • Calculate the midpoints (midX and midY) of the upperRight and lowerLeft coordinates, which effectively divides the area into four smaller rectangles.
    • Recursively calculate the number of ships in each of the four quadrants that the original rectangle is divided into:
      • The bottom-left quadrant from lowerLeft to (midX, midY).
      • The top-right quadrant from (midX + 1, midY + 1) to upperRight.
      • The top-left quadrant from (lowerLeft.x, midY + 1) to (midX, upperRight.y).
      • The bottom-right quadrant from (midX + 1, lowerLeft.y) to (upperRight.x, midY).

This function effectively uses recursion and spatial subdivision to determine the presence of ships and incrementally decompose the problem into more manageable sub-problems until it identifies all ships within the entire rectangle or confirms their absence.

Comments

No comments yet.