We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ships in a Rectangle

Number: 1233

Difficulty: Hard

Paid? Yes

Companies: Bloomberg

Problem Description

Given a rectangular region defined by its bottom left and top right coordinates, determine the number of ships located within that rectangle. You can only use the provided API function Sea.hasShips(topRight, bottomLeft) which returns whether there is at least one ship in the given rectangle. Note that each ship is at an integer coordinate and at most 10 ships are present in the overall region. The challenge is to efficiently count ships using at most 400 API calls.

Key Insights

  • Use a divide-and-conquer approach by recursively partitioning the search area into smaller subrectangles.
  • If the API call Sea.hasShips returns false for a given rectangle, that entire region can be skipped.
  • When the rectangle is reduced to a single point (bottomLeft equals topRight) and a ship exists there, count it as 1.
  • Careful partitioning minimizes the number of API calls, keeping the solution within the call limit.
  • The constraint of at most 10 ships guarantees that deep recursion happens only along branches that actually contain a ship.

Space and Time Complexity

Time Complexity: O(4^(min(log(range width), log(range height)))) in the worst-case scenario, but practically it is much lower due to pruning from the hasShips API and the small number of ships. Space Complexity: O(log(max(range width, range height))) due to recursion stack depth.

Solution

We solve the problem using a recursive, divide-and-conquer algorithm. At each step, we check if the rectangle (defined by bottomLeft and topRight) contains any ships using the Sea.hasShips API. If not, we return 0. If the rectangle is a single point and a ship exists there, we return 1. Otherwise, we split the rectangle into four smaller subrectangles by calculating the midpoints along the x- and y-axes.

The four subrectangles (if valid) are:

  1. Bottom-left quadrant: from bottomLeft to (midX, midY)
  2. Top-right quadrant: from (midX+1, midY+1) to topRight
  3. Top-left quadrant: from (bottomLeft.x, midY+1) to (midX, topRight.y)
  4. Bottom-right quadrant: from (midX+1, bottomLeft.y) to (topRight.x, midY)

The recursive calls are only made on subrectangles that are valid (i.e. the bottom left coordinates are not greater than the top right ones). This minimization of searches ensures we do not exceed the allowed API calls.

Code Solutions

# Python solution using divide and conquer

class Sea:
    # assume Sea.hasShips is implemented externally
    @staticmethod
    def hasShips(topRight, bottomLeft):
        pass

class Solution:
    def countShips(self, sea: 'Sea', topRight: list, bottomLeft: list) -> int:
        # Recursive helper function to count ships in the region defined by bottomLeft and topRight.
        def count_in_region(bottomLeft, topRight):
            # If there is no ship in the current rectangle, return 0.
            if not sea.hasShips(topRight, bottomLeft):
                return 0
            # If the rectangle is reduced to a single point, then there is exactly one ship.
            if bottomLeft == topRight:
                return 1
            # Calculate midpoint coordinates.
            midX = (bottomLeft[0] + topRight[0]) // 2
            midY = (bottomLeft[1] + topRight[1]) // 2
            total = 0
            # Bottom-left quadrant: from bottomLeft to (midX, midY)
            total += count_in_region(bottomLeft, [midX, midY])
            # Top-right quadrant: from (midX+1, midY+1) to topRight
            if midX + 1 <= topRight[0] and midY + 1 <= topRight[1]:
                total += count_in_region([midX+1, midY+1], topRight)
            # Top-left quadrant: from (bottomLeft.x, midY+1) to (midX, topRight.y)
            if midY + 1 <= topRight[1]:
                total += count_in_region([bottomLeft[0], midY+1], [midX, topRight[1]])
            # Bottom-right quadrant: from (midX+1, bottomLeft.y) to (topRight.x, midY)
            if midX + 1 <= topRight[0]:
                total += count_in_region([midX+1, bottomLeft[1]], [topRight[0], midY])
            return total

        return count_in_region(bottomLeft, topRight)
        
# Example usage:
# sea = SeaImplementation(...)
# sol = Solution()
# count = sol.countShips(sea, [4,4], [0,0])
← Back to All Questions