4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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>

\$\endgroup\$
  • 2
    \$\begingroup\$ 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] = ... \$\endgroup\$ – Kruga Feb 22 at 12:13
  • \$\begingroup\$ @Kruga Good point, i was not on the ball. \$\endgroup\$ – Blindman67 Feb 22 at 12:40
  • \$\begingroup\$ 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? \$\endgroup\$ – thadeuszlay Feb 22 at 18:05
  • \$\begingroup\$ @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. \$\endgroup\$ – Blindman67 Feb 22 at 19:53
  • \$\begingroup\$ May I ask what is your favorite language and why? \$\endgroup\$ – thadeuszlay Feb 22 at 20:09
2
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.