Number of Ships in a Rectangle
HardAsked by:
3 views
Topics:
ArraysRecursion
Each ship is located at an integer point on the sea represented by a cartesian plane, and each ship is surrounded by an impenetrable rectangular hull. We can only know the region each ship is located at, but we cannot know the exact position of the ship inside the hull.
Given the two integer arrays topRight and bottomLeft representing the top-right and bottom-left coordinates of the area we want to search, return the number of ships present in that area.
You may assume that:
- Initially, all of the sea is water (except for the ships).
- The coordinate (0,0) is the top-left corner of the map.
- You can only access the area where
0 <= bottomLeft[0] <= topRight[0] <= 2000and0 <= bottomLeft[1] <= topRight[1] <= 2000.
Implement the function int countShips(int[][] topRight, int[][] bottomLeft) that takes the top-right and bottom-left coordinates of the area to search and returns the number of ships present in that area.
Notice that assignment will be checked on the total number of calls to your API, so please think carefully about whether to make too many calls. You are not allowed to call the API more than 400 times per test case.
Example 1:
Input: ships = [[1,1],[2,2],[2,0],[1,0]], topRight = [2,2], bottomLeft = [0,0] Output: 3 Explanation: From the example above, the ships are located at [[1,1],[2,2],[2,0],[1,0]]. Using the function countShips(topRight = [2,2], bottomLeft = [0,0]) will return 3 since there are three ships found in the defined area.
Example 2:
Input: ships = [[1,1],[2,2],[2,0],[1,0]], topRight = [2,2], bottomLeft = [2,1] Output: 1 Explanation: Using the function countShips(topRight = [2,2], bottomLeft = [2,1]) will return 1 since there is only one ship found in the defined area.
Constraints:
ships.length <= 10000 <= ships[i][0], ships[i][1] <= 2000topRight.length == 2bottomLeft.length == 20 <= bottomLeft[0] <= topRight[0] <= 20000 <= bottomLeft[1] <= topRight[1] <= 2000
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the exact signature of the API function I can call to determine if a rectangle contains any ships?
- Can multiple ships exist at the same exact integer coordinate? And if so, how would the `hasShips` API reflect that for a single-point query?
- The 400 API call limit seems to be the main challenge. Is there a tighter constraint on the maximum number of ships I can expect within any single queried area, separate from the global limit of 1000 ships?
- Are the boundaries of the query rectangle inclusive? For instance, if a ship's coordinate is on the edge defined by `topRight`, is it considered inside the area?
- Can the input rectangle be a degenerate shape, such as a single point where `topRight` equals `bottomLeft`, or a line where one pair of coordinates is equal?
Brute Force Solution
Approach
The most straightforward way to find all the ships is to meticulously check every single possible spot within the rectangular sea. We will systematically go through the entire area, point by point, and for each one, we'll ask if a ship is located right there.
Here's how the algorithm would work step-by-step:
- Imagine the entire rectangular sea as a large grid of tiny, individual points.
- We'll start our search at one corner of this grid.
- For the very first point, we'll use our special tool to check a tiny square area that covers only that single point.
- If the tool tells us there's a ship in that tiny spot, we add one to our total count of ships found.
- After checking that point, we move to the next point right beside it in the same row and repeat the check.
- We continue this process, checking every single point across the first row.
- Once we finish a row, we move down to the beginning of the next row and do the exact same thing all over again.
- We keep repeating this for all the rows until every single point in the entire sea has been individually checked.
- The final count we have at the end is our answer for the total number of ships.
Code Implementation
class Solution(object):
def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
total_ships_found = 0
# Iterate through every single coordinate in the rectangle to ensure no potential ship location is missed.
for current_x_coordinate in range(bottomLeft.x, topRight.x + 1):
for current_y_coordinate in range(bottomLeft.y, topRight.y + 1):
# Create a tiny 1x1 rectangle for the current point to isolate it for the ship check.
current_point = Point(current_x_coordinate, current_y_coordinate)
if sea.hasShips(current_point, current_point):
# A positive result for a single point confirms a unique ship is at these coordinates.
total_ships_found += 1
return total_ships_foundBig(O) Analysis
Time Complexity
O(W * H) – The time complexity is driven by the exhaustive search across every single point in the rectangular sea. Let W be the width and H be the height of the rectangle. The described approach iterates through each of the H rows, and for each row, it checks every one of the W points within it. This systematic, point-by-point check is equivalent to a nested loop structure processing the entire grid. The total number of checks is the product of the width and height, W * H, which simplifies to a time complexity of O(W * H).
Space Complexity
O(1) – The algorithm's memory usage is driven by a single counter for the total ships and a few variables to track the current row and column coordinates being checked. This iterative approach systematically scans the grid point by point without needing to store which locations have been visited. No auxiliary data structures, such as arrays or hash maps, are created to hold intermediate results. Since the number of variables used remains fixed regardless of the total number of points in the rectangle, the auxiliary space complexity is constant.
Optimal Solution
Approach
Instead of checking every single point on the map, which would be very slow, this approach works by checking large areas at once. If a large area has no ships, we can ignore it entirely and save a lot of time, only focusing our search on the regions that we know contain ships.
Here's how the algorithm would work step-by-step:
- Start with the entire rectangular sea you are given. First, ask the special tool if there are any ships at all within this large rectangle.
- If the tool says 'no', you're done with this area. There's nothing to count here.
- If the tool says 'yes', you need to look closer. If the rectangle is already the smallest possible size (a single point), then you've found a ship! Count it.
- If the rectangle is larger than a single point and contains ships, split it into four smaller, equal quadrants: top-left, top-right, bottom-left, and bottom-right.
- Now, repeat the whole process for each of these four smaller rectangles. Ask the tool about each one to see if it contains ships.
- The total number of ships is the sum of all the ships you find by investigating these smaller and smaller pieces.
- This method of dividing and conquering allows you to quickly eliminate huge empty parts of the sea and zoom in only on the locations where ships actually are.
Code Implementation
class Solution(object):
def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
# If the API confirms no ships are in this rectangle, we can prune this entire search branch.
if not sea.hasShips(topRight, bottomLeft):
return 0
# If the search area has been reduced to a single point that contains ships, we've found one.
if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
return 1
mid_coordinate_x = (bottomLeft.x + topRight.x) // 2
mid_coordinate_y = (bottomLeft.y + topRight.y) // 2
# To pinpoint ships, we divide the rectangle and recursively search the four resulting quadrants.
top_left_quadrant_ships = self.countShips(sea, Point(mid_coordinate_x, topRight.y), Point(bottomLeft.x, mid_coordinate_y + 1))
top_right_quadrant_ships = self.countShips(sea, topRight, Point(mid_coordinate_x + 1, mid_coordinate_y + 1))
bottom_left_quadrant_ships = self.countShips(sea, Point(mid_coordinate_x, mid_coordinate_y), bottomLeft)
bottom_right_quadrant_ships = self.countShips(sea, Point(topRight.x, mid_coordinate_y), Point(mid_coordinate_x + 1, bottomLeft.y))
return top_left_quadrant_ships + top_right_quadrant_ships + bottom_left_quadrant_ships + bottom_right_quadrant_shipsBig(O) Analysis
Time Complexity
O(n log K) – The primary cost is the number of recursive calls, which is determined by the number of ships, n, and the size of the grid. The algorithm avoids checking every point by only exploring quadrants confirmed to contain ships through the provided tool. For each of the n ships, the algorithm must perform a search by recursively dividing the grid, where the number of divisions is proportional to the logarithm of the grid's total area. The total number of operations is approximately n (the number of ships) times log K (the recursive depth, where K is the number of points in the grid), which simplifies to O(n log K).
Space Complexity
O(log N) – The space complexity is determined by the maximum depth of the recursion call stack, which is the primary source of auxiliary memory. This algorithm recursively divides the rectangle, creating a new stack frame for each call until it reaches a single point or an empty sub-rectangle. The number of times a rectangle's side can be halved is logarithmic relative to its length. Therefore, if N is the length of the longer side of the initial sea, the maximum depth of the recursion stack will be proportional to log N, resulting in O(log N) auxiliary space.
Edge Cases
| Case | How to Handle |
|---|---|
| The query rectangle is a single point, where topRight equals bottomLeft. | The base case of the recursion handles this by making one hasShips call and returning 1 or 0 accordingly. |
| The query rectangle contains no ships at all. | The solution should make a single hasShips call on the initial rectangle, which returns false, and then immediately returns 0. |
| Ships are located exactly on the boundaries used for splitting the rectangle into quadrants. | The splitting logic must be precise, assigning each point on a boundary to exactly one sub-rectangle to prevent missing ships or double counting. |
| The query rectangle is a one-dimensional line, either horizontal or vertical. | The 2D divide-and-conquer approach naturally handles this, as two of the four recursive sub-quadrants will always be invalid and terminate immediately. |
| All ships in the query rectangle are clustered in a single point or a very small area. | The recursion quickly prunes the three empty quadrants at each level, resulting in an efficient search with a low number of API calls. |
| Ships are maximally dispersed, for example, at the corners of a large rectangle. | This represents a worst-case scenario for API calls where recursion proceeds down multiple branches, severely testing the solution's efficiency against the API call limit. |
| A recursive call is made with an invalid rectangle where a bottomLeft coordinate is greater than a topRight coordinate. | The recursive function must have a base case to check for and handle these invalid rectangles by returning 0 to correctly terminate that search path. |
| The query rectangle is the largest possible area, from [0,0] to [2000,2000]. | The solution's scalability is tested as recursion will reach its maximum depth, requiring efficient pruning to stay within the API call limit. |
The query rectangle is a single point, where topRight equals bottomLeft.
How to Handle:
The base case of the recursion handles this by making one hasShips call and returning 1 or 0 accordingly.
The query rectangle contains no ships at all.
How to Handle:
The solution should make a single hasShips call on the initial rectangle, which returns false, and then immediately returns 0.
Ships are located exactly on the boundaries used for splitting the rectangle into quadrants.
How to Handle:
The splitting logic must be precise, assigning each point on a boundary to exactly one sub-rectangle to prevent missing ships or double counting.
The query rectangle is a one-dimensional line, either horizontal or vertical.
How to Handle:
The 2D divide-and-conquer approach naturally handles this, as two of the four recursive sub-quadrants will always be invalid and terminate immediately.
All ships in the query rectangle are clustered in a single point or a very small area.
How to Handle:
The recursion quickly prunes the three empty quadrants at each level, resulting in an efficient search with a low number of API calls.
Ships are maximally dispersed, for example, at the corners of a large rectangle.
How to Handle:
This represents a worst-case scenario for API calls where recursion proceeds down multiple branches, severely testing the solution's efficiency against the API call limit.
A recursive call is made with an invalid rectangle where a bottomLeft coordinate is greater than a topRight coordinate.
How to Handle:
The recursive function must have a base case to check for and handle these invalid rectangles by returning 0 to correctly terminate that search path.
The query rectangle is the largest possible area, from [0,0] to [2000,2000].
How to Handle:
The solution's scalability is tested as recursion will reach its maximum depth, requiring efficient pruning to stay within the API call limit.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
