Filling array with averages

Question

Im wondering about a problem I have in Javascript. I have a scenario where I need to fill gaps in an array with averages of the surrounding values. Let me give an example:

Array: 1, 2, 3, ,4, 5

In this particular case I would need to fill the gap with average of the surrounding numbers, i.e. 3.5. I think this is relatively easy to do.

However, I also need to make sure this works when there is more subsequent gaps in the array.

Example: 1, 2, 3, , , 5, 6

In this case the two gaps should be filled with the average of 3 and 5, resulting in ... 3, 4, 4, 5.

The moment I got stuck was when I tried iterating the array and filling the gaps because I filled the first gap with 4, but at that moment, the surrounding numbers for the second gap were 4 (the original gap) and 5, so I ended up with

... 3, 4, 4.5, 5, ...

which is not what I need.

Im using jQuery to iterate the array and get the values from a table.

This is how Im loading the array:

var list = [];
$('#mytable > tbody  > tr').each(function() {
  $this = $(this);
  list.push(eval($this.find("input.number").val());
}

Now I need to iterate and fill the gaps in "list"

Answer 1

Another functional recursive version

const arr = [1,2,3,,,5,6]

function fill([head,...tail], lastNotNull, holeWidth = 0){
  if (tail.length === 0 ) return head
  if (head === undefined) return fill(tail, lastNotNull, ++holeWidth)
  return Array(holeWidth).fill((lastNotNull+head)/2).concat(head).concat(fill(tail, head))
}

console.log(fill(arr))

Explanation:

First parameter of fill function is destructured into head and tail. Head represent the current value and tail next values

• Base case: tail empty -> we just return head
• If current value head is undefined, we recurse increasing the size of the hole and keeping the last not null value, to compute the average
• In all other cases we fill the hole with the average, we add the current value and then recurse onto remaining array, resetting lastNotNull to head and holeWidth to 0 with default value

I feel that the last step could be optimized in terms of execution time but I like the fact that it's compact and clear (if already comfortable with recursion)

Bonus: I love the fact that the hole is filled with the Array.prototype.fill function

Answer 2

There is a recursive way to do this, Basically it counts the empty spots between two values and divides the difference over these empty spots:

var arr = [1, , , , 3, 4, , , 6];

for( var i = 0; i < arr.length; i++ ){
    if( arr[ i ] === undefined )
        arr[ i ] = avg( arr[ i - 1 ], arr.slice( i + 1, arr.length ), 1 );
}

function avg( low, arr, recursion ){
    if( arr[ 0 ] === undefined )
        return avg( low, arr.slice( 1, arr.length ), recursion + 1 );

    return low + ( ( arr[0] - low ) / ( recursion + 1 ) );
}

console.log( arr );

Works like a charm:

arr = [1, 2, 3, ,4, 5] => [1, 2, 3, 3.5, 4, 5]
arr = [1, 2, 3, , , 5, 6] => [1, 2, 3, 3.6665, 4.3333, 5, 6]
arr = [1, , , , 3, 4, , , 6] => [1, 1.5, 2, 2.5, 3, 4, 4.6667, 5.3334, 6]

Answer 3

Interesting question that made me think a bit.

My first idea was to use map but I found that it does not consider holes. Fixed that with Array.from that converts holes to undefined

I was hoping to find a more concise solution but I'm posting it anyways

function fillMissing(a){
  return Array.from(a).map((e,i)=> e !== undefined ? e : averageAround(i,a))
}

const averageAround = (index, array) => average(before(index, array), after(index, array))
const average = (a, b) => (a+b)/2
const before = findFirstNotUndefined.bind(null, -1)
const after = findFirstNotUndefined.bind(null, 1)

function findFirstNotUndefined(direction, index, array){
  if (array[index] !== undefined) return array[index]
  return findFirstNotUndefined(direction, index+direction, array)
}

console.log(fillMissing([1, 2, 3, , , 5, 6]));

Some thoughts:

• recursive call to findFirstNotUndefined is in tail call position
• findFirstNotUndefined should be memoizable, (maybe) useful for large holes
• average around can be written point free style but not without adding another function or importing some fp library like ramda
• Modifying the signature of averageAround like (_, index, array), it can be used directly in the map: Array.from(a).map(averageAround). Cool to read even if it computes the average on every value ((val + val)/2)

Answer 4

You could iterate the sparse array and store the last index and value. If a gap is found, the gap is filled with the average of the last value and the actual value.

function fill(array) {
  array.reduce((last, v, i, a) => {
      var j, avg;
      if (last.index + 1 !== i) {
          avg = (v + last.value) / 2;
          for (j = 1; j < i - last.index; j++) {
              a[last.index + j] = avg;
          }
      }
      return { index: i, value: v };
  }, { index: -1 });
  return array;
}

console.log(fill([1, 2, 3, , , 5, 6]));
console.log(fill([1, , , , , , 6]));
console.log(fill([1, , , , 3, 4, , , 6]));

Answer 5

You can do something like this using simple iteration.

function fillMissing(arr) {
  // array for storing result
  var res = [];
  // iterate over the array
  for (i = 0; i < arr.length; i++) {
    // if undefined then call the function to calculate average or set the value
    res[i] = arr[i] == undefined ? calculateAverage(arr, i) : arr[i];
  }
  return res;
}

function calculateAverage(arr1, i) {
  // set preve and next value as nearest element
  var prev = arr1[i - 1],
    next = arr1[i + 1],
    j = 1; // variable for iterating
  
  // iterate to find out nearest defined value
  // after the element
  while (prev == undefined) { prev = arr1[i - ++j]; }
    
  j = 1; //  reset for next iteration
  // iterate to find out nearest defined value
  // before the element
  while (next == undefined) { next = arr1[i + ++j]; }
  
  //find average and return
  return (prev + next) / 2;
}



console.log(fillMissing([1, 2, 3, , , 5, 6]));
console.log(fillMissing([1, 2, 3, , , 5, 6]));
console.log(fillMissing([1, , , , , , 6]));
console.log(fillMissing([1, , , , 3, 4, , , 6]));

Answer 6

Try this code

var x = "1, 2, 3, ,4, 5";

var y = "1, 2, 3, , , 5, 6";

var z = "1, , , , , , 6";

var q = "1, , , , 3, 4, , , 6";

function removeSpace(str) {
  return str.replace(/ /g, "");
}

function splitString(str) {
  return str.split(',');
}

function fill(str) {
  var z = removeSpace(str);
  var zPrime = splitString(z);

  for (var i = 0; i < zPrime.length; i++) {
    if (zPrime[i] == "") {
      if (i + 1 < zPrime.length && zPrime[i + 1] != "") {
        zPrime[i] = (Number(zPrime[i - 1]) + Number(zPrime[i + 1])) / 2;
      } else {
        var j = i + 1;
        while (j < zPrime.length && zPrime[j] == "") j++;
        var tp = (j < zPrime.length) ? Number(zPrime[j]) : 0;
        var dn = (i - 1 > -1) ? Number(zPrime[i - 1]) : 0;
        for (var k = i; k < j; k++) {
          zPrime[k] = ((tp + dn) / 2) + '';
        }
      }
    }
  }
  return zPrime;
}

console.log(fill(x));
console.log(fill(y));
console.log(fill(z));
console.log(fill(q));

Answer 7

Here's one possible implementation:

function fill(arr) {
  while (arr.includes(undefined)) {
    const startIndex = arr.findIndex(num => num === undefined);
    const endIndex = arr.findIndex((num, i) => i >= startIndex && num !== undefined);
    const avg = (arr[startIndex - 1] + arr[endIndex]) / 2;
    for (let i = startIndex; i < endIndex; i++) arr[i] = avg;
  }
  return arr;
}
console.log(fill([1, 2, 3, , , 5, 6]));
console.log(fill([1, , , , , , 6]));
console.log(fill([1, , , , 3, 4, , , 6]));