Let
be the number of animals,
the size of the board and
the largest distance.
Solution for 1D board
To solve the 1D board, we first sort the coordinates and then perform a sweep-line algorithm. We keep track of two pointers: head and tail. When the head is pointing to an element with coordinate
, the tail is pointing to the first element with coordinate greater than or equal to
.
For each position of head, we add
to the total result. As we advance head to the next element, we can easily adjust tail to point to the required element.
The time complexity of this algorithm is
for sorting, and
for sweeping.
Solution for 2D board
To solve the 2D version of the problem, we first consider the distance formula:

The formula above will resolve to one of the following four formulas:

It is easy to see that the distance is always equal to the largest of these four values. As
and
represent the "diagonal coordinates" of point
we substitute:
and
.
Now, we can rewrite the distance formula in terms of
and
:

or shorter:

After substitution, we sort all the points by the first coordinate (
) increasingly and perform a sweep-line algorithm similar to the one-dimensional case. Since each point
between head and tail satisfies the inequality
, we only need to find out for how many of them the inequality
is satisfied as well. To calculate that value, we keep all points (their
coordinates) between head and tail in either an interval tree or a binary indexed tree data structure.
The time complexity of the algorithm implemented with a binary indexed tree data structure is
for sorting, and
for sweeping, where
is the upper bound on the coordinates.
Solution for 3D board
Inspired by our 2D solution we start with the distance formula once again and obtain:

Again, we perform a sweep-line algorithm on the
coordinate while keeping all of the points between head and tail in a 3D binary indexed tree in order to count the number of points
satisfying inequalities
,
and
.
The time complexity of the algorithm is
for sorting, and
for sweeping.
It is worth mentioning that we can use this solution to solve all types of boards. We just assign any constant value (1 for example) to each of the missing coordinates and implement a 3D binary indexed tree using either dynamic memory allocation, or using a one-dimensional array and manually mapping the 3-dimensional space to elements of the array.
Comments