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

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.

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>

• Is it really a good idea to fill an array with unshift? It sounds inefficient. You could easily put each element at its correct position right away. res[end-start] = ... Commented Feb 22, 2019 at 12:13
• @Kruga Good point, i was not on the ball. Commented Feb 22, 2019 at 12:40
• The resulting code is simply beautiful and solves the problem efficiently. Masterful I have to say. Hmm....may I have a tiny question? I just noticed, is there a reason why you chose an if/else over a ternary operator? Commented Feb 22, 2019 at 18:05
• @thadeuszlay Eeeck my 3rd stuff up for the day... :(.The original version unshifted to the array rather than assigned to an array index and thus was not suited for a ternary. Good call res[idx--] = (-arr[start] > arr[end] ? arr[start++] : arr[end--]) ** 2; is far more concise. Commented Feb 22, 2019 at 19:53
• May I ask what is your favorite language and why? Commented Feb 22, 2019 at 20:09

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;