Problem Description

The "Number of Ships in a Rectangle" problem provides you with a hidden sea, in which ships are placed at integer coordinates. You are given an API Sea.hasShips(topRight, bottomLeft) that returns True if there is at least one ship within the rectangle defined by the topRight and bottomLeft coordinates (inclusive), and False otherwise. Your task is to implement a function countShips(sea, topRight, bottomLeft) that returns the number of ships in the given rectangle.

• You cannot access the actual ship locations directly—only through the Sea.hasShips API.
• Ships do not overlap and are placed at integer points.
• You want to minimize the number of calls to hasShips due to performance constraints.
• The rectangle is defined by two coordinates: topRight and bottomLeft, each as a pair [x, y].
• All coordinates are integers between 0 and 1000 inclusive.

Thought Process

At first glance, you might consider checking every possible coordinate within the rectangle to see if a ship exists there. However, this brute-force approach is highly inefficient, especially since the rectangle can be large (up to 1,000,001 points). Moreover, the only way to interact with the sea is through the hasShips API, which checks for any ship in a given area, not individual points.

To optimize, we need a strategy that leverages the power of hasShips to rule out large empty regions quickly and focus only on areas where ships might be present. This leads us to consider a divide-and-conquer approach, similar to how binary search narrows down a search space efficiently.

By splitting the current rectangle into smaller subrectangles and only recursing into those that contain ships, we can dramatically reduce the number of hasShips calls and avoid unnecessary checks.

Solution Approach

We use a recursive divide-and-conquer algorithm to efficiently count the number of ships in the rectangle:

1. First, check if the rectangle defined by topRight and bottomLeft contains any ships using hasShips. If not, return 0.
2. If the rectangle is reduced to a single point (i.e., topRight == bottomLeft), and hasShips returns True, return 1 (there is a ship at this point).
3. Otherwise, split the rectangle into smaller subrectangles. A common approach is to divide it into four quadrants by finding the midpoints of the x and y coordinates.
4. Recursively count ships in each quadrant, summing the results.
5. This process continues until all possible ships are counted, with minimal hasShips calls.

This approach is efficient because it prunes large empty regions quickly and only explores areas where ships are present.

• We use recursion to break down the problem.
• Base case: the rectangle is a single point.
• Recursive case: divide into four smaller rectangles.
• We avoid unnecessary work by immediately returning 0 if hasShips is False for a region.

Example Walkthrough

Suppose the rectangle is from bottomLeft = [0, 0] to topRight = [2, 2], and ships are at [0, 0] and [1, 2].

1. Call hasShips([2, 2], [0, 0]), which returns True (since there are ships).
2. The rectangle is not a single point, so we find the midpoints: midX = 1, midY = 1.
3. Split into four quadrants:
   • Q1: [0, 0] to [1, 1]
   • Q2: [2, 0] to [2, 1]
   • Q3: [0, 2] to [1, 2]
   • Q4: [2, 2] to [2, 2]
4. For each quadrant, call hasShips:
   • Q1: hasShips([1, 1], [0, 0]) returns True (ship at [0, 0]).
   • Q2: hasShips([2, 1], [2, 0]) returns False.
   • Q3: hasShips([1, 2], [0, 2]) returns True (ship at [1, 2]).
   • Q4: hasShips([2, 2], [2, 2]) returns False.
5. Recurse into Q1 and Q3:
   • Q1: Eventually reduces to [0, 0] where hasShips([0, 0], [0, 0]) returns True, so count 1.
   • Q3: Eventually reduces to [1, 2] where hasShips([1, 2], [1, 2]) returns True, so count 1.
6. Sum all counts: 1 (Q1) + 0 (Q2) + 1 (Q3) + 0 (Q4) = 2 ships.

This walkthrough shows how the algorithm narrows down to the actual ship locations with minimal hasShips calls.

Time and Space Complexity

Brute-force approach:

• Would require checking every point in the rectangle: O((x2 - x1 + 1) * (y2 - y1 + 1)) calls to hasShips.
• This is infeasible for large rectangles.

• Each recursive call splits the rectangle into four smaller rectangles.
• If there are k ships, the recursion tree will have O(k log N) nodes, where N is the maximum side length.
• In the worst case (ships are spread out), the number of hasShips calls is O(k log N).
• Space complexity is O(log N) due to recursion stack depth.

This is much more efficient than brute-force, especially when the number of ships is small compared to the size of the rectangle.

Summary

The "Number of Ships in a Rectangle" problem demonstrates the power of divide-and-conquer in optimizing search problems. By recursively splitting the rectangle and leveraging the hasShips API to prune empty regions, we efficiently count the number of ships without checking every point. This approach minimizes API calls and handles large search spaces gracefully, making it both elegant and practical for similar search-and-prune scenarios.

Code Implementation

# This is the Sea's API interface.
# You should not implement it, or speculate about its implementation
# class Sea:
#     def hasShips(self, topRight: List[int], bottomLeft: List[int]) -> bool:

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):
            return 0
        if x1 == x2 and y1 == y2:
            return 1

        midX = (x1 + x2) // 2
        midY = (y1 + y2) // 2

        count = 0
        # bottom left
        count += self.countShips(sea, [midX, midY], [x1, y1])
        # bottom right
        count += self.countShips(sea, [x2, midY], [midX + 1, y1])
        # top left
        count += self.countShips(sea, [midX, y2], [x1, midY + 1])
        # top right
        count += self.countShips(sea, [x2, y2], [midX + 1, midY + 1])

        return count
      

/**
 * // This is the Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *   public:
 *     bool hasShips(vector<int> topRight, vector<int> bottomLeft);
 * };
 */

class Solution {
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        int x1 = bottomLeft[0], y1 = bottomLeft[1];
        int x2 = topRight[0], y2 = topRight[1];
        if (x1 > x2 || y1 > y2) return 0;
        if (!sea.hasShips(topRight, bottomLeft)) return 0;
        if (x1 == x2 && y1 == y2) return 1;

        int midX = (x1 + x2) / 2;
        int midY = (y1 + y2) / 2;

        int count = 0;
        // bottom left
        count += countShips(sea, {midX, midY}, {x1, y1});
        // bottom right
        count += countShips(sea, {x2, midY}, {midX + 1, y1});
        // top left
        count += countShips(sea, {midX, y2}, {x1, midY + 1});
        // top right
        count += countShips(sea, {x2, y2}, {midX + 1, midY + 1});
        return count;
    }
};
      

/**
 * // This is the Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface Sea {
 *     public boolean hasShips(int[] topRight, int[] bottomLeft);
 * }
 */

class Solution {
    public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
        int x1 = bottomLeft[0], y1 = bottomLeft[1];
        int x2 = topRight[0], y2 = topRight[1];
        if (x1 > x2 || y1 > y2) return 0;
        if (!sea.hasShips(topRight, bottomLeft)) return 0;
        if (x1 == x2 && y1 == y2) return 1;

        int midX = (x1 + x2) / 2;
        int midY = (y1 + y2) / 2;

        int count = 0;
        // bottom left
        count += countShips(sea, new int[]{midX, midY}, new int[]{x1, y1});
        // bottom right
        count += countShips(sea, new int[]{x2, midY}, new int[]{midX + 1, y1});
        // top left
        count += countShips(sea, new int[]{midX, y2}, new int[]{x1, midY + 1});
        // top right
        count += countShips(sea, new int[]{x2, y2}, new int[]{midX + 1, midY + 1});
        return count;
    }
}
      

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * function Sea() {
 *     Sea.prototype.hasShips = function(topRight, bottomLeft) {
 *         ...
 *     };
 * }
 */

/**
 * @param {Sea} sea
 * @param {number[]} topRight
 * @param {number[]} bottomLeft
 * @return {number}
 */
var countShips = function(sea, topRight, bottomLeft) {
    let x1 = bottomLeft[0], y1 = bottomLeft[1];
    let x2 = topRight[0], y2 = topRight[1];
    if (x1 > x2 || y1 > y2) return 0;
    if (!sea.hasShips(topRight, bottomLeft)) return 0;
    if (x1 === x2 && y1 === y2) return 1;

    let midX = Math.floor((x1 + x2) / 2);
    let midY = Math.floor((y1 + y2) / 2);

    let count = 0;
    // bottom left
    count += countShips(sea, [midX, midY], [x1, y1]);
    // bottom right
    count += countShips(sea, [x2, midY], [midX + 1, y1]);
    // top left
    count += countShips(sea, [midX, y2], [x1, midY + 1]);
    // top right
    count += countShips(sea, [x2, y2], [midX + 1, midY + 1]);
    return count;
};