square the elements of a sorted list and give the output in sorted order

Question

Given a sorted list of integers, square the elements and give the output in sorted order.

For example, given [-9, -2, 0, 2, 3], return [0, 4, 4, 9, 81].

My solution 1:

const square = el => el * el;
const sortAsc = (a, b) => a - b;
const sortSquare = list => list
  .map(square)
  .sort(sortAsc);

console.log(sortSquare([-9, -2, 0, 2, 3]));

My solution 2:

const sortSquare2 = list => {
  list.sort((a, b) => Math.abs(a) - Math.abs(b));
  for (let i = 0; i < list.length; i++) {
    list[i] = Math.pow(list[i], 2);
  }
  return list;
};

console.log(sortSquare2([-9, -2, 0, 2, 3]));

Is there a faster solution? I have the feeling you can do something with the fact that the list is sorted to begin with. But I can't think of a good one.

Answer 1

If you start at both ends and compare these values, you can step down towards the center, unshifting the values, squaring them and unshifting them to the resulting array.

You don't need to square the values until you add them to the array. You can compare to find the greater value by negating the left side.

One \$O(n)\$ solution is as follows

function sortSquares(arr) {
    const res = [];
    var start = 0; end = arr.length - 1, idx = end;
    while (start <= end) {
        res[idx--] = (-arr[start] > arr[end] ? arr[start++] : arr[end--]) ** 2;
    }
    return res;
}

// Test code
[
    [-9,-5,-0.5,0.6,1, 2, 3,8],
    [1, 2, 3,8],
    [-10, -8, -3, -1, -1, 1, 1, 1],    
    [0.6,1, 2, 3,8],
    [-9,-6,-3,-2,-1],
    [-9,-6,-3,-2,-1,1,2,3,6,9],
].forEach(a => log(a, sortSquares(a)));


function log(data, data1) {
   data = "[" + data + "] -=>> [" + data1 + "]";
   info.appendChild(Object.assign(document.createElement("div"),{textContent: data}));
}

<code id="info"></code>

Answer 2

I can give you a functional programming and ES6 related thing instead of a performance improvement

---

Pointfree

Pointfree is a programming paradigm in which you try to avoid the argument you want to transform.

So we could avoid sortSquare = list => ...

const sortSquare = compose(
  sort(sortAsc), 
  map(square)
)

Where sort and map are curried functions and compose is a composition of two functions in the form of \$f ∘ g\$ which means \$f(g(x))\$

const map = f => xs => xs.map(f)
const sort = f => xs => xs.sort(f)

const compose = (f, g) => x => f(g(x))

const square = el => el ** 2
const sortAsc = (a, b) => a - b

const sortSquare = compose(
  sort(sortAsc),
  map(square)
)

console.log(sortSquare([-9, -2, 0, 2, 3]));

---

Exponentiation in ES6

Since ES6 it is possible to use the **-operator.

const square = el => el * el;

const square = el => el ** 2;