Java – How to find a subset of size k such that the minimum distance between values is maximum

dynamic programmingjava

Suppose I have a sorted array which contains n integers.
How do I find subset of size k such that the minimum distance between all pairs of integers in the subset is maximized, I mean they are at maximal distance.

example: array a[]={1,2,6,7,10} and k=3,
subset = {1,6,10}, the minimum distance is 4 between 10 and 6.
Wrong subsets:
{1,7,10} , minimum distance is 3
{1,2,6} , minimum distance is 1

My first thought was to get all the combinations in the size of k, then calculate the distance of each one. But the time complexity would be O(n!), and the interviewer doesn't like it. Dynamic Programming is the hint he gave me, but I still have no idea.

He suggested that I can start from a[0], find a[0]+x=Y also in the array… and then Y+x and so on k-1 times, also kth element will be a[n-1], but I couldn't get him. I don't know why there must be such a x, like in the example above, the correct answer is {1,6,10}, the distance between 1 and 6 is 5, and it's 4 between 6 and 10, then what should x be?

Best Answer

For some given lists and sizes, it may have many correct answers.

I would try a greedy algorithm instead of backtracking: Given an sub-selection, if one wants to extend it to an extra element, one simply have to select the new one, since the maximum of minimal distances can only decrease as the number of elements increases. Complexity: O(k*n*n), which is a better than O(n!).

If you ignore special cases (size > list.size, etc.):

List<Int> maxmin(List<Int> l, int size)
{
   Int head = l.subList(0, 1);
   List<Int> tail = l.subList(1, l.size());
   more(head, tail, size-1);
}

private List<Int> more(List<Int> selected, List<Int> available, int size)
{
   if(size == 0) return selected;
   else
   {
      int max = maxByMin(available, selected);
      selected.add(max);
      available.remove(max);
      return more(selected, available, size-1);
   }
}

private int maxByMin(List<Int> candidates, List<Int> elements)
{
   int maxMin = Integer.MIN_VALUE;
   int maxVal = candidates(0);

   for(int candidate : candidates)
   {
      int minDist = Integer.MAX_VALUE;

      for(int element : elements)
      {
         int dist = math.abs(candidate, element);
         if(dist < minDist)
         {
             minDist = dist;
         }
      }

      if(minDist > maxMin)
      {
         maxMin = minDist;
         maxVal = candidate;
      }
   }
   return candidate;
}

In Scala:

def maxmin(l: Seq[Int], size: Int): Seq[Int] =
{
  def more(selected: Seq[Int], reminder: Seq[Int], size: Int): Seq[Int] =
  {
     if(size == 0) selected
     else
     {
        val max = reminder.maxBy(x => selected.map(y => math.abs(y - x)).min)
        more(selected :+ max, reminder diff Seq(max), size-1)
     }
  }

  more(Seq(l.head), l.tail, size-1)
}

I did not checked the Java code, but the Scala one seems OK. Otherwise, please provide a counter-example because that probably means I not understood the problem.

Related Topic