# Find minimum buckets required to hold all the elements in an array

• I was asked this question in Microsoft

You are given an array of integers and bucket capacity k(sum of the elements in the bucket should not exceed k), return minimum buckets required to hold all the elements in the array. You are required to return list of buckets not number of buckets.

Example.
Arr = [7,3,5,4,1] and bucket size is 9.
return --> [ [7,1],[5,4],[3]]. if multiple answer is possible with same number of buckets then return any of them.

Followup Question ---> in case of multiple answer return buckets such that maximum difference between sum of elements in the buckets should be minimum.

so for above example return [ [7],[5,1],[4,3] ],
1st bucket sum = 7
2nd bucket sum = 6
3rd bucket sum = 7

maximum difference between bucket =1 (which is minimum).

• For the first part, a greedy approach seems about right. I simply try to pack in as much as I can into every bucket. However I make sure that I try to add at least one small number for every big number I add. This makes sure I don't waste buckets by only adding maximally or minimally.

``````vector<vector<int>> guessBuckets(vector<int> &arr, int maxCap) {
vector<vector<int>> ans;

sort(arr.begin(), arr.end());

int i = 0, j = arr.size()-1, sum = 0;
vector<int> temp;

while(i <= j) {

while(i <= j) {
// try to add bigger number
if(sum + arr[j] <= maxCap) {
temp.push_back(arr[j]);
sum += arr[j--];
}

// try to add smaller number
if(i <= j && sum + arr[i] <= maxCap) {
temp.push_back(arr[i]);
sum += arr[i++];
} else
}

ans.push_back(temp);

temp.clear();
sum = 0;
}

return ans;
}
``````

For `arr[] = [7, 3, 5, 4, 1]`, it returns answer as `[[7, 1], [5, 3], [4]]`.

Dunno about the followup question. Maybe we can do something with the mean of the array. For example, for the aforementioned case:

• The sum of the array is `20`.
• If each bucket could hold a max sum of `9`, then we need about `ceil(20/9) == 3` buckets in an ideal world. (Incidentally this is also the correct answer. NOTE: This is not guaranteed to be true every time.)
• So the mean sum inside each bucket should be around `floor(20/3) to ceil(20/3) == 6 to 7`. If you look at the optimal answer `[[7], [5,1], [4,3]]`, one can see very well that each bucket has a sum in the mean range.

Perhaps that is the secret: Running a greedy algorithm with a maximum sum up to the mean and not the maximum capacity. However I don't see how it ensures the total minimum number of buckets.

Honestly, determining a global optimal bucket configuration sounds like a NP problem. Will sit on it, I guess.

• ``````public static void listBuckets(int[] in, int bucketsize) {
Arrays.sort(in);
List<List<Integer>> finalL = new ArrayList<List<Integer>>();
int sum = 0;
int i = 0, j = in.length - 1;
List<Integer> inL = new ArrayList<Integer>();
while (i < j) {
while (sum + in[j] <= bucketsize) {
sum += in[j--];
}

while(sum+in[i] <= bucketsize) {
sum += in[i++];
}

inL = new ArrayList<>();
sum = 0;
}

if(i == j && in[i] < bucketsize) {