Sorting array of arrays based on means

Question

I just finished taking a coding assessment and had trouble with sorting an array of arrays by their means. Each group should contain a set of indices (i,j,etc.) such that the corresponding arrays all (a[i],a[j],etc.) all have the same mean.

For example:

let a = [[3,3,4,2],
         [4,4],
         [4,0,3,5],
         [3,3]
       ]
function sortMean(a) {
let newArr = a.sort(function (a, b) {
  let sum1 = a.reduce(function (c, d) {
    return c + d;
  });
  let sum2 = b.reduce(function (c, d) {
    return c + d;
  });

  let mean1 = sum1 / a.length;
  let mean2 = sum2 / b.length;
  return mean1 - mean2;
});

sortMean(a)
expected output: [[0,2,3],[1]]

So far I am able to sort by their means, but am having issues with grouping them into arrays and their indices.

Answer 1

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.