Hackerrank: "Cut the sticks" Javascript solution

Question

I took a stab at solving this problem from Hackerrank in Javascript, and would like your valuable feedback as to time/space complexity and just about any additional improvements.

Problem URL: https://www.hackerrank.com/challenges/cut-the-sticks

My JS implementation:

function main() {   
    var n = parseInt(readLine());
    arr = readLine().split(' ');
    arr = arr.map(Number);
    
    arr = arr.sort(function(a,b){ return a-b; });
    
    function cut(barr){
        if(barr.length>0){//checks array length
            var min = barr[0]; //save min value in current array
            process.stdout.write(barr.length+'\n'); //write initial array length
            var b = [];
            for(var i=0; i<barr.length; i++){ //iterate over array
                var result = barr[i]-min; //math ops
                if(result>0){
                    b.push(result); //build new array if value is greater than 0
                }
            }
            
            cut(b); // call cut operation again with new array
        }else{
            return; //halt operation if no values left to check for
        }
    }
    
    cut(arr);
    
}

Answer 1

Once the array is sorted, as you have it, the crux of this algorithm is simply:

subtract the smallest element from every element, then remove elements that equal 0

With es6 and method chaining, this can be expressed in a single line of code. The rest is just the boilerplate and a condition to check when the recursion is finished -- all similar to what you have now.

Here's the rewrite:

function main() {
  readLine();
  const input = readLine().split(' ').map(Number).sort((a,b) => a-b );
  cut(input);

  function cut(arr) {
    if (!arr.length) return;
    console.log(arr.length);
    cut(arr.map(x => x - arr[0]).filter(x => x > 0)); // <-- the essence of the algorithm
  }
}

I should also point out that the above, as well as your solution, runs in \$O(n^2)\$. You can in fact do better: \$O(n\log n)\$. Because after the array is sorted, you can solve the problem with a single pass through the array, as follows:

function main() {
  readLine();
  const input = readLine().split(' ').map(Number).sort((a,b) => a-b );
  cut(input, input[0]);

  function cut(arr, min) {
    if (!arr.length) return;
    console.log(arr.length);
    while(arr[0] == min) arr.shift();
    cut(arr, arr[0]);
  }
}

Here we're taking advantage of the fact that after each cut, the elements that are removed are precisely those equal to the minimum element. And to produce the output required for the problem, we notice that we don't actually have to do the cuts for every element of the list. We merely have to remove the elements of 0 length.