Find the element with the most "neighbors" in the sequence

Question

Suppose we have a sequence S with n elements <x1,x2,...,xn> . A pair of elements xi,xj is considered neighbors if |xi-xj|<d , and d given distance between two neighbors. So, how do you know the element that has most of the neighbors in the sequence?

(A simple way sorts a sequence and then calculates the number of each element, but the time complexity is quite large):

 O(nlogn) 

Can you help me find a better way to reduce time complexity?

Answer 1

O(N log N) not "pretty big"; log is a very slowly growing function!

It is impossible to do in time less than O(N) , since you have to read the entire input. You can do this in O(N) if you know the range of numbers, in which case you can use any of the O(N) sorting methods (for example, counting sorting sorting / sorting, sorting by the radix method).

---

Here a is O(dN) -time, O(N + k) O(dN) spatial sort-based count solution implemented in Java.

 static int mostNeighbors(int k, int d, int... nums) { boolean[] appears = new boolean[k]; int[] neighborCount = new int[k]; int most = 0; for (int num : nums) { appears[num] = true; for (int i = num - d + 1; i < num + d; i++) { if (i < 0 || i >= k) continue; if (++neighborCount[i] > neighborCount[most] && appears[i]) { most = i; } } } return most; } // ... System.out.println(mostNeighbors(10, 2, 0,0,0,2,2,2)); // prints 0 System.out.println(mostNeighbors(10, 2, 0,0,0,2,2,2,1)); // prints 1 System.out.println(mostNeighbors(10, 2, 1,2,3,4,5,3)); // prints 2 

Basically, for each num it increases neighborCount[num-d+1..num+d-1] , which are in the range from 0..k-1 . Not all numbers in this range are actually displayed in the array, therefore appears used to track this. most used to track the best search results.