Let ~N~ be the number of animals, ~M~ the size of the board and ~D~ 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 ~x~, the tail is pointing to the first element with coordinate greater than or equal to ~x-D~.

For each position of head, we add ~\mathrm{head}-\mathrm{tail}~ 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 ~\mathcal O(N \log N)~ for sorting, and ~\mathcal O(N)~ for sweeping.

Solution for 2D board

To solve the 2D version of the problem, we first consider the distance formula:

$$\displaystyle \operatorname{dist}(P, Q) = |P_x - Q_x| + |P_y - Q_y|$$

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

$$\displaystyle \begin{align*} \operatorname{dist}(P, Q) &= P_x - Q_x + P_y - Q_y = (P_x + P_y) - (Q_x + Q_y) \\ \operatorname{dist}(P, Q) &= P_x - Q_x - P_y + Q_y = (P_x - P_y) - (Q_x - Q_y) \\ \operatorname{dist}(P, Q) &= -P_x + Q_x + P_y - Q_y = (Q_x - Q_y) - (P_x - P_y) \\ \operatorname{dist}(P, Q) &= -P_x + Q_x - P_y + Q_y = (Q_x + Q_y) - (P_x + P_y) \end{align*}$$

It is easy to see that the distance is always equal to the largest of these four values. As ~P_x + P_y~ and ~P_x - P_y~ represent the "diagonal coordinates" of point ~P~ we substitute:

~P_{d_1} := P_x + P_y~ and ~P_{d_2} := P_x - P_y~.

Now, we can rewrite the distance formula in terms of ~d_1~ and ~d_2~:

$$\displaystyle \operatorname{dist}(P, Q) = \max(P_{d_1} - Q_{d_1}, P_{d_2} - Q_{d_2}, Q_{d_2} - P_{d_2}, Q_{d_1} - P_{d_1})$$

or shorter:

$$\displaystyle \operatorname{dist}(P, Q) = \max(|P_{d_1} - Q_{d_1}|, |P_{d_2} - Q_{d_2}|)$$

After substitution, we sort all the points by the first coordinate (~d_1~) increasingly and perform a sweep-line algorithm similar to the one-dimensional case. Since each point ~P~ between head and tail satisfies the inequality ~\mathrm{head}_{d_1} - P_{d_1} \le D~, we only need to find out for how many of them the inequality ~|\mathrm{head}_{d_2} - P_{d_2}| \le D~ is satisfied as well. To calculate that value, we keep all points (their ~d_2~ 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 ~\mathcal O(N \log N)~ for sorting, and ~\mathcal O(N \log M)~ for sweeping, where ~M~ 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:

$$\displaystyle \begin{array}{rrcl} & \operatorname{dist}(P, Q) &=& \max\left( |P_{f_1} - Q_{f_1}|, |P_{f_2} - Q_{f_2}|, |P_{f_3} - Q_{f_3}|, |P_{f_4} - Q_{f_4}| \right), \\ \text{where:} \\ & P_{f_1} &:=& P_x + P_y + P_z \\ & P_{f_2} &:=& P_x + P_y - P_z \\ & P_{f_3} &:=& P_x - P_y + P_z \\ & P_{f_4} &:=& P_x - P_y - P_z \end{array}$$

Again, we perform a sweep-line algorithm on the ~f_1~ 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 ~P~ satisfying inequalities ~|\mathrm{head}_{f_2} - P_{f_2}| \le D~, ~|\mathrm{head}_{f_3} - P_{f_3}| \le D~ and ~|\mathrm{head}_{f_4} - P_{f_4}| \le D~.

The time complexity of the algorithm is ~\mathcal O(N \log N)~ for sorting, and ~\mathcal O(N \log^3 M)~ 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.