A few weeks ago on reddit I read a question that asked for a solution to a fairly simple looking array balancing problem. But it turns out that a satisfactory solution isn't easy to come by, and I didn't see any offered in the comments. In fact, I'm not even completely happy with the solution I'll present in this post.

The problem

The requirements are as follows: write a function that takes a number and divides that number among the elements of a given array such that it brings the difference between the elements to be as small as possible.

To make it more concrete, let's set up our test cases and our expected values. Our function will be called .balance and it will be added to the Array prototype:

Two important caveats:

  • An element should never decrease in value to balance out the rest of the array.
  • The output should have non-whole numbers if it produces the least difference between the elements of the array.
[2, 3, 0].balance(5)    // => Expected output: [3.3, 3.3, 3.3]
[2, 3, 0].balance(1)    // => Expected output: [2, 3, 1]
[5, 7].balance(4)       // => Expected output: [8, 8]
[2, 0, 0, 0].balance(2) // => Expected output: [2, 0.66, 0.66, 0.66]

The creator of the reddit post wanted to simulate the behavior of adding liquid to a grid containing various amounts of liquid and making sure the added liquid balanced itself out.

The quick and dirty way

I posted my solution to the problem in the comments section here. A naïve (but fast) implementation that others suggested was to calculate the average value of the array if the parameter of .balance was added to the array, and then set every element of the array equal to that value. The suggested averaging algorithm would look like this:

Array.prototype.balance = function(input) {
  let currentSum = this.reduce((accumulator, el) => {
    { return accumulator + el }
  })
  let avg = (currentSum + input)/this.length
  return this.map(() => avg)  
}

[2, 3, 0].balance(4) // =>    [3,3,3]        PASS
[2, 3, 0].balance(1) // =>    [2, 2, 2]      FAIL
[5, 7].balance(4) // =>       [8,8]          PASS
[2, 0, 0, 0].balance(1) // => [ 1, 1, 1, 1 ] FAIL

This implementation finishes in O(n) time and passes our first and third test cases but fails the second and fourth. In fact, any time the average of the array is less than any of the elements in the array, the method will fail. A more comprehensive solution is needed.

The slow but sure solution

Because we're trying to distribute a value as fairly as possible among the elements of an array, we can assume that we'll always be "giving" to the lowest values in the array. Written out step by step, it's this:

  1. Find the lowest value in the array.
  2. Find all the values in the array that have that value and store their indexes.
  3. Divide 1 by the number of elements that contain the lowest value. Store that value.
  4. Add the number calculated in step three to each of the elements you found in step 2.
  5. Decrement the parameter by 1.
  6. If the parameter is greater than 0, go to step 1.

Because we're making the locally optimal choice for each 'point' we're distributing among the array, this would constitute a greedy algorithm. An implementation of this algorithm in JavaScript might look like this:

Array.prototype.balance = function(input) {
  let ret = this;

  for (let i = input; i > 0; i--){
    // Find the lowest value of the array
    let lowestVal = Math.min(...ret);

    // Find indexes of lowest values in the array
    let indexesOfLowestVals = [];
    ret.map((el, index) => {
      if (el === lowestVal){
        indexesOfLowestVals.push(index);
      }
    });

    // Distribute 1 point among the lowest values equally
    let avgValue = 1/indexesOfLowestVals.length;
    indexesOfLowestVals.map(index => ret[index] += avgValue);
  }

  // Round the final elements to two decimal places and return.
  return ret.map(el => { return parseFloat(el.toFixed(2)) });
};

This passes the following tests:

[2, 3, 0].balance(4) // => [3,3,3]
[2, 3, 0].balance(5) // => [3.3, 3.3, 3.3]
[2, 3, 0].balance(1) // => [2,3,1]
[5, 7].balance(4) // => [8,8]
[2, 0, 0, 0].balance(2); // => [2, 0.66, 0.66, 0.66]

As with anything written in JavaScript you can test this method in your browser's console.

Conclusion

This method is slow. We pass through the entire array once just to find the lowest value, then again to record the indexes that match the lowest value, and then distribute to the indexes we recorded, which could possibly be the entire array. We would do that entire process 77 times if we called .balance with 77, with one additional pass through to do the rounding. I'd be interested to see a better implementation, however, even in a different language.