Coding Problem: Balancing a Scale

4 min readFeb 2, 2018

Code edited on January 14, 2019 after a year of coding experience. Refactored into various functions and explicit variables to increase readability.

Link to full solution: https://repl.it/@etea13/Balancing-a-scale

This is a problem I saw recently on Coderbyte about balancing a scale — here is the problem:

You are given an array of two strings as an input. The first string is an unsorted array of two positive integers to represent the balance scale. The second string is an unsorted array of positive integers to represent weights available. Example: ["[5, 9]", "[1, 2, 6, 7]"]The task is to balance the scale (the first string) with the least amount of weights and values using at most two weights, in ascending order. In the above example, the solution should return "2,6". If no solution is found, return 'not possible'. Other possible scenarios include two weights added to only one side, using only one weight, and one weight on each sides. There will be only one unique solution.Input & Output:(i) ["[3, 7]", "[1, 2, 7]"] => "not possible"(ii) ["[5, 9]", "[1, 2, 6, 7]"] => "2,6"(iii) ["[13, 4]", "[1, 2, 3, 6, 14]"] => "3,6" (iv) ["[3, 4]", "[1, 2, 7, 7]"] => "1"(v) ["[1, 5]", "[1, 11, 7, 5]"] => "1,5" (not "7, 11")

After completing the challenge, I’ve realized no step-by-step guide is available so I took a look at the top solutions by users. A majority of solutions involved using two for loops or a for loop and indexOf for finding solutions using more than one weight, creating an exponential time complexity.

First Step: Converting the string to actual arrays for easier access

The format of the input is something like this: [“[left, right]”, “[w1, w2, w3, …]”

They could have made our lives easier by giving us arrays of two arrays! But to convert it to arrays of sorted arrays, we would have to traverse through both strings in the array. We are sorting it so it will return the combination of the smallest weights.

Using match:

function strToArr(str) {
    return str.split(',').map(el => parseInt(el.match(/\d+/g)[0])).sort((a, b) => a - b > 0)
}

If you don’t feel comfortable in using regex, you can also traverse the string character by character. Regex match is O(n), n being total integers, and sort is usually O(nlogn), depending on browser.

Breaking down the above code into extra steps:

function strToArr(str) {
    const arr = []
    str.split(',').forEach(el => {
      const match = el.match(/\d+/g);
      arr.push(match[0]);
    });    return arr.sort((a, b) => a - b > 0);
}

Second Step: Create an ES6 Map to store counts of weights

We will initialize a map as we traverse the array of weights, we will update count in map.

//weights: [w1, w2, w3, ...], mapOfWeights: new Map()function createWeightMap (weightsAvailable) {
  const weightsMap = new Map();
  weightsAvailable.forEach((weight, index) => {
    if(!weightsMap.get(weight)) weightsMap.set(weight, 0)
    weightsMap.set(weight, weightsMap.get(weight) + 1)
  });  return weightsMap;
};

This will take O(n - 2), n being total integers, and minus 2 for the weights on the scale. Space complexity at this point is O(n) for the weights available.

Third Step: Using Only One Weight

It’s the most ideal to work on this scenario first because it uses less time so if it fulfills this condition, we should return the solution immediately so we don’t proceed on to the next conditions.

//balance: [left, right]function balanceWithOneWeight (balance, weightsMap, differenceBetweenWeights) {
  return weightsMap.has(differenceBetweenWeights) && differenceBetweenWeights;
};

This will take O(1) since a map’s access time is O(1). That is one of the perks of using a map.

Fourth Step: Traversing the Array of Weights

We will now traverse the weights array and this can be done using a for loop.

for(let i = 0; i < weights.length; i++) {
        count = mapOfWeights.get(weights[i])
        mapOfWeights.set(weights[i], count - 1)
}

Each time we loop through, we want to decrease the count of the current element because we want to prevent the element from being used a second time if it doesn’t have duplicates.

Condition Two: Adding two weights on one side

To check if adding two weights on one side will solve the problem, you should check if adding the current weight and the next weight to balance[0] (lower amount) will equal to balance[1].

if(weights[i] + weights[i + 1] + balance[0] === balance[1]) {
        answer = `${weights[i]},${weights[i + 1]}`
        i = weights.length
}

If it fulfills this ‘if’ statement, it will set answer to the weights and it will set i to weights.length to exit the for loop.

Condition Three: Adding one weight on each side

The last condition is adding a weight on each side. To do this, you should find the difference between adding balance[0] and the current weight and balance[1] (balance[1] - (balance[0] + current weight]) and take the absolute value. After, check if the difference is in the map.

else if(mapOfWeights.get(diff) > 0) {
        answer = weights[i] > diff ? `${diff},${weights[i]}` : `${weights[i]},${diff}`
        i = weights.length
}

Fifth Step: Returning the answer

After the for loop is done, return the answer. Answer is initialized as ‘not possible’ so if it never fulfills the if/else if conditions, ‘not possible’ would be returned.

return answer

To decrease the O(n²) time complexity to O(n), I did a tradeoff using ES6 Map. If you don’t want to use a map, like many others, you might want to use Javascript built-in methods like indexOf, includes or two for loops.