Sorting array of arrays based on means

Array#reduce is your friend here. Simply take each average and build an object grouping on key (average) mapped to values that are arrays of all indices matching that average. Use the third argument to reduce to get the index.

After grouping, use Object.values to chop off the keys and you're left with the result.

const a = [
  [3,3,4,2],
  [4,4],
  [4,0,3,5],
  [3,3]
];
  
const sum = a => a.reduce((a, e) => a + e, 0);
const avg = a => sum(a) / a.length;

const result = Object.values(a.reduce((a, e, i) => {  
  const mean = avg(e);
  
  if (!a[mean]) {
    a[mean] = [];
  }
  
  a[mean].push(i);
  return a;
}, {}));

console.log(result);

Note also that your sort approach might work, but would be O(n log(n)) time at best when this should be doable in linear time (disregarding the decimal thing mentioned above). Also, you're computing averages for arrays many times in the comparator which amounts to a lot of extra work--it's best to do that computation up-front.

Since averages are typically decimals, the problem becomes more interesting if you need to use an epsilon to bucket. I'd ask about that if this was an interview. You may be able to use rounding to bin close-enough floats which would still be linear.

I was doing the same challenge using Python:

def meangroup(a):
    mean_list = []
    group_mean = []
    for idx,i in enumerate(a):
        mean_value = sum(i)/len(i)
        if mean_value in mean_list:
            group_mean[mean_list.index(mean_value)].append(idx)
        else:
            group_mean.append([idx])
        mean_list.append(mean_value)
    return  group_mean

I found this challenge to be interesting so I gave it a try. I wrote it in Java but it can easily be converted to any language you want.

int[][] arr = { { 3, 3, 4, 2 }, { 4, 4 }, { 4, 0, 3, 5 }, { 3, 3 } };

Map<Integer, List<Integer>> map = new TreeMap<>();

for (int i = 0; i < arr.length; i++) {
    int mean = mean(arr[i]);
    if (map.containsKey(mean)) {
        List<Integer> l = map.get(mean);
        l.add(i);
        map.put(mean, l);
    } else {
        List<Integer> l = new ArrayList<>();
        l.add(i);
        map.put(mean, l);
    }
}

Choose TreeMap as it keeps the keys in ascending order (sorted). And this Map will hold means as keys and indices as values in a List. Then we iterate over the array, find mean, add it to the map and index in a list to the map, and if map already contains the mean, then add the index to the existing list.

int finArr[][] = new int[map.values().size()][]; //this will hold the final answer--arrays of indices. 

List<Integer> keys = new ArrayList<>(map.keySet());

map.keySet() would return keys in ascending order (because we chose to create a Map of type TreeMap above), but we want to instantly convert it to ArrayList because we cannot pull values from a Set using index. And we also need index to feed arrays at correct locations into the final array.

for (int i = 0; i < keys.size(); i++) {
    finArr[i] = map.remove(keys.get(i)).stream().mapToInt(val -> val).toArray();
}

In above for loop, we are basically pulling values (which is a List) out of map, and converting that List to primitive int array.

System.out.print("[ ");
for (int[] is : finArr) {
    System.out.print(Arrays.toString(is) + " ");
}
System.out.println("]");

output: [ [0, 2, 3], [1] ]

The mean meathod:

private static int mean(int[] arr) {
    int sum = 0;
    for (int i : arr) {
        sum += i;
    }
    return sum / arr.length;
}

Bonus::

This variation of InsertionSort can sort the array based on mean values.

for (int i = 1; i < arr.length; i++) {
    int[] kk = arr[i];
    int key = mean(arr[i]);
    int j = i - 1;
    while (j > -1 && mean(arr[j]) > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = kk;
}

for (int[] is : arr) {
    System.out.println(Arrays.toString(is));
}

output: [3,3,3,4]

I love Kotlin <3

fun main() {
    val arr = arrayOf(arrayOf(3, 3, 4, 2), arrayOf(4, 4), arrayOf(4, 0, 3, 5), arrayOf(3, 3))

    val map = mutableMapOf<Int, MutableList<Int>>()

    for ((i, mArray) in arr.withIndex()) {
        val mean = mArray.average().toInt()
        val meanList: MutableList<Int> = map[mean] ?: mutableListOf()
        meanList.add(i)
        map[mean] = meanList
    }

    println(map.values.toList())
}