# Choosing one element from each partition that minimize the difference between max and min

Given an unsorted array $$A$$ that contains $$n$$ elements of numbers. Also $$A$$ partitioned to $$k$$ lists $$A_1,A_2,A_3,\dots,A_k$$, each contains at most nearly $$\frac{n}{k}$$ elements. We choose exactly one elements from each $$A_i$$ so that difference between maximum and minimum element minimized. Can this be done in $$O(n\log k)$$ time?

I think this can't be done in better than $$\Omega (n\log n)$$ because assume already we know the value of our optimal solution, name it $$t$$. Also assume $$A$$ not partitioned and our goal is find two elements $$a$$ and $$b$$ from $$A$$ such $$|a-b|=t$$. We know that the lower bound of a such problem is $$\Omega (n\log n)$$. Could we say my argument is true or not?

• Your argument is in right direction, however, it is not completely formal. There are $k$ partitions; and you have used the same notation in $|a-b| = k$. I am assuming, you are considering $k = 1$ partitions for proving your lower bound argument. Also, this lower bound is only for comparison based model. Mar 1 at 11:59