I have an unsorted array of size n and I need to find k-1 divisors so every subset is of the same size (like after the array is sorted).
I have seen this question with k-1=3. I guess I need the median of medians and this is will take o(n). But I think we should do it k times so o(nk).
I would like to understand why it would take o(n logk).
For example: I have an unsorted array with integers and I want find the k'th divisors which is the k-1 integers that split the array into k (same sized) subarrays according to their values.
If I have [1, 13, 6, 7, 81, 9, 10, 11] the 3=k dividers is [7 ,11] spliting to [1 6, 9 10 13 81] where every subset is big as 2 and equal.
You can use a divide-and-conquer approach. First, find the (k-1)/2th divider using the median-of-medians algorithm. Next, use the selected element to partition the list into two sub-lists. Repeat the algorithm on each sub-list to find the remaining dividers.
The maximum recursion depth is O(log k) and the total cost across all sub-lists at each level is O(n), so this is an O(n log k) algorithm.