LC: 1274. Number of Ships in a Rectangle - spiralgo/algorithms GitHub Wiki
1274. Number of Ships in a Rectangle:
The Essence:
Although the question asks for the number of ships in the biggest rectangle, we do not have a method to give us the number.
We just have a method that we can ask if there is a ship in any rectangle with given coordinates: Sea.hasShips(topRight, bottomLeft)
This case implies that we need to divide the biggest rectangle into smaller ones recursively and call hasShips for each.
Therefore we need to focus on an approach based on the divide-and-conquer strategy.
Details:
It is quite clear that we need a recursive function in which we will keep dividing the rectangle, count each encounter in iterations and return the total number of encounters.
You can find quite a straight-forward yet elegant implementation here: