LeetCode 1274 - Number of Ships in a Rectangle

The problem presents an interactive scenario where ships are placed at integer coordinates on a Cartesian plane. You do

leetcodehardarraydivide-and-conquerinteractive

LeetCode Problem 1274

Difficulty: 🔴 Hard
Topics: Array, Divide and Conquer, Interactive

Solution

Problem Understanding

The problem presents an interactive scenario where ships are placed at integer coordinates on a Cartesian plane. You do not know their positions, and each coordinate contains at most one ship. You are given two points representing the bottom-left and top-right corners of a rectangle, and you need to determine the number of ships contained within that rectangle.

The only way to gather information about ship positions is through the API Sea.hasShips(topRight, bottomLeft), which returns a boolean indicating whether there is at least one ship inside the given rectangle. The challenge is to count all ships using as few calls as possible, with a hard limit of 400 calls. The problem guarantees that there are at most 10 ships in any queried rectangle, which allows for efficient divide-and-conquer strategies.

Key edge cases include querying a rectangle with no ships, rectangles that are just one point (where topRight equals bottomLeft), and rectangles with ships clustered at corners. The guarantee that topRight != bottomLeft simplifies the problem slightly by avoiding zero-area rectangles in the initial input.

Approaches

The brute-force approach would be to query every integer point within the rectangle individually. For each point (x, y) in the range, we could call hasShips(Point(x, y), Point(x, y)) and count the ships. While correct, this is highly inefficient because the area of the rectangle could be up to 1001 × 1001 points, leading to over a million API calls. This clearly exceeds the limit of 400 calls and is therefore impractical.

The optimal approach leverages a divide-and-conquer strategy. The key insight is that if a rectangle contains at least one ship, you can subdivide it into four smaller rectangles (quadrants) and recursively check each. If a rectangle contains no ships, you can immediately skip it. By repeatedly subdividing, the algorithm zooms in on individual points where ships exist. Since there are at most 10 ships, the recursion depth and number of calls remain manageable. The strategy is analogous to a quadtree search, efficiently pruning empty regions.

Approach Time Complexity Space Complexity Notes
Brute Force O(W * H) O(1) Check every point individually; infeasible for large rectangles
Divide and Conquer O(S * log(W*H)) O(log(W*H)) Recursively split rectangle into quadrants; S = number of ships

Algorithm Walkthrough

  1. Begin with the input rectangle defined by bottomLeft and topRight.
  2. Call sea.hasShips(topRight, bottomLeft). If this returns False, return 0 immediately since there are no ships.
  3. If the rectangle represents a single point (topRight.x == bottomLeft.x and topRight.y == bottomLeft.y) and hasShips returns True, return 1 since there is exactly one ship.
  4. Otherwise, divide the rectangle into four smaller rectangles using the midpoint along the x and y axes. Compute midpoints as midX = (topRight.x + bottomLeft.x) // 2 and midY = (topRight.y + bottomLeft.y) // 2.
  5. Recursively call the function on each quadrant:
  • Bottom-left quadrant
  • Bottom-right quadrant
  • Top-left quadrant
  • Top-right quadrant
  1. Sum the results from the four recursive calls to get the total number of ships in the current rectangle.
  2. Return this total.

Why it works: The divide-and-conquer ensures that each recursive call either detects no ships or isolates a single ship at the point level. By summing all results, we correctly count all ships without repeatedly querying empty regions. The recursion terminates because each division reduces the rectangle area, eventually reaching single points.

Python Solution

# """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
#class Sea:
#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
#
#class Point:
#    def __init__(self, x: int, y: int):
#        self.x = x
#        self.y = y

class Solution:
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
        if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y:
            return 0
        
        if not sea.hasShips(topRight, bottomLeft):
            return 0
        
        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
            return 1
        
        midX = (topRight.x + bottomLeft.x) // 2
        midY = (topRight.y + bottomLeft.y) // 2
        
        count = 0
        count += self.countShips(sea, Point(midX, midY), bottomLeft)
        count += self.countShips(sea, Point(topRight.x, midY), Point(midX + 1, bottomLeft.y))
        count += self.countShips(sea, Point(midX, topRight.y), Point(bottomLeft.x, midY + 1))
        count += self.countShips(sea, topRight, Point(midX + 1, midY + 1))
        
        return count

The implementation first checks if the rectangle is invalid or empty. If the rectangle has no ships, it immediately returns zero. For rectangles of size 1×1, it returns one if a ship is present. Otherwise, it divides the rectangle into quadrants, recursively counts ships in each, and sums the results.

Go Solution

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * type Sea struct {
 *     func hasShips(topRight, bottomLeft []int) bool {}
 * }
 */

func countShips(sea Sea, topRight, bottomLeft []int) int {
    if topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1] {
        return 0
    }
    if !sea.hasShips(topRight, bottomLeft) {
        return 0
    }
    if topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1] {
        return 1
    }
    
    midX := (topRight[0] + bottomLeft[0]) / 2
    midY := (topRight[1] + bottomLeft[1]) / 2
    
    count := 0
    count += countShips(sea, []int{midX, midY}, bottomLeft)
    count += countShips(sea, []int{topRight[0], midY}, []int{midX + 1, bottomLeft[1]})
    count += countShips(sea, []int{midX, topRight[1]}, []int{bottomLeft[0], midY + 1})
    count += countShips(sea, topRight, []int{midX + 1, midY + 1})
    
    return count
}

In Go, slices are used to represent points. The recursive logic mirrors Python, with careful attention to slice construction for quadrants. There is no need for classes since Go functions can pass slices directly.

Worked Examples

Example 1:

ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]

Recursive Call Rectangle hasShips? Count
1 [0,0]-[4,4] True 3 (sum of subcalls)
2 [0,0]-[2,2] True 2
3 [0,0]-[1,1] True 1
4 [2,0]-[2,1] False 0
5 [0,2]-[1,2] False 0
6 [2,2]-[2,2] True 1
7 [3,3]-[4,4] True 1

Sum = 3 ships.

Example 2:

ships = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,0]

The algorithm quickly prunes empty large areas, recursively subdividing only where hasShips returns true. Total count = 3.

Complexity Analysis

Measure Complexity Explanation
Time O(S * log(W*H)) Each ship may trigger recursion down log(W*H) levels; S ≤ 10
Space O(log(W*H)) Recursion stack proportional to rectangle divisions

The recursion efficiently prunes empty regions, ensuring that the 400-call limit is never exceeded due to the guarantee of ≤10 ships.

Test Cases

# test cases
# Example 1
assert Solution().countShips(Sea([[1,1],[2,2],[3,3],[5,5]]), Point(4,4), Point(0,0)) == 3  # Multiple ships in range

# Example 2
assert Solution().countShips(Sea([[1,1],[2,2],[3,3]]), Point(1000,1000), Point(0,0)) == 3  #