Number of Ships in a Rectangle - Practice Coding Problems

Number of Ships in a Rectangle - Problem

This is an interactive problem. Each ship is located at an integer point on the sea represented by a cartesian plane, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points: the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Input & Output

Example 1 — Basic Rectangle Search

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

› Output: 3

💡 Note: Rectangle from [0,0] to [4,4] contains ships at [1,1], [2,2], and [3,3]. Ship at [5,5] is outside the rectangle.

Example 2 — Smaller Rectangle

$ Input: ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [2,2], bottomLeft = [1,1]

› Output: 2

💡 Note: Rectangle from [1,1] to [2,2] contains ships at [1,1] and [2,2] only.

Example 3 — No Ships in Range

$ Input: ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [0,0], bottomLeft = [0,0]

› Output: 0

💡 Note: Single point [0,0] contains no ships.

Constraints

On the given rectangle, there are at most 10 ships.
The length of each dimension of the rectangle is at most 1000.
You can make at most 400 calls to hasShips.
topRight != bottomLeft

Visualization

Tap to expand

Understanding the Visualization

Input Ships & Rectangle

Ships at coordinates and search rectangle bounds

API Constraint

Use hasShips(topRight, bottomLeft) efficiently (≤400 calls)

Count Result

Return number of ships within rectangle bounds

Key Takeaway

🎯 Key Insight: Use divide and conquer to minimize API calls by only searching regions that contain ships

Asked in

G Google 45 f Facebook 32

The key insight is to use divide and conquer to efficiently search only regions containing ships. Instead of checking each coordinate individually, recursively divide the rectangle into quadrants and only explore areas where hasShips returns true. Best approach is divide and conquer with Time: O(log(area) × ships), Space: O(log(area)).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Point	O(w × h)	O(1)	Check each coordinate individually to count ships
Divide and Conquer - Recursive Search	O(log(area) × ships)	O(log(area))	Recursively divide rectangle into quarters, only search areas containing ships

Brute Force - Check Every Point — Algorithm Steps

Iterate through all x coordinates from bottomLeft[0] to topRight[0]
For each x, iterate through all y coordinates from bottomLeft[1] to topRight[1]
Call hasShips for each single coordinate
Count total ships found

Visualization

Tap to expand

Step-by-Step Walkthrough

Grid Setup

Mark all coordinates in the rectangle

Sequential Check

Check each coordinate one by one

Count Ships

Count found ships and return total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SHIPS 10

typedef struct {
    int ships[MAX_SHIPS][2];
    int count;
} Sea;

int hasShips(Sea* sea, int topRight[2], int bottomLeft[2]) {
    for (int x = bottomLeft[0]; x <= topRight[0]; x++) {
        for (int y = bottomLeft[1]; y <= topRight[1]; y++) {
            for (int i = 0; i < sea->count; i++) {
                if (sea->ships[i][0] == x && sea->ships[i][1] == y) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int solution(Sea* sea, int topRight[2], int bottomLeft[2]) {
    int count = 0;
    for (int x = bottomLeft[0]; x <= topRight[0]; x++) {
        for (int y = bottomLeft[1]; y <= topRight[1]; y++) {
            int point[2] = {x, y};
            if (hasShips(sea, point, point)) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    Sea sea;
    sea.count = 4;
    sea.ships[0][0] = 1; sea.ships[0][1] = 1;
    sea.ships[1][0] = 2; sea.ships[1][1] = 2;
    sea.ships[2][0] = 3; sea.ships[2][1] = 3;
    sea.ships[3][0] = 5; sea.ships[3][1] = 5;
    
    int topRight[2] = {4, 4};
    int bottomLeft[2] = {0, 0};
    
    printf("%d\n", solution(&sea, topRight, bottomLeft));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(w × h)

Must check every coordinate in width × height rectangle

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables for counting and iteration

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Point — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler