1
\$\begingroup\$

The task:

Given an array of integers, return a new array where each element in the new array is the number of smaller elements to the right of that element in the original input array.

For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1, 0], since:

  • There is 1 smaller element to the right of 3
  • There is 1 smaller element to the right of 4
  • There are 2 smaller elements to the right of 9
  • There is 1 smaller element to the right of 6
  • There are no smaller elements to the right of 1
const lst = [3, 4, 9, 6, 1];

My solutions:

const numberOfSmallerElem = lst => lst.map((x,i) => lst.slice(i + 1).reduce((acc,y) => y < x ? ++acc : acc, 0));    
console.log(numberOfSmallerElem(lst));

function numberOfSmallerElem2(lst) {
  for (let i in lst) {
    lst[i] = lst.slice(i).reduce((acc,y) => y < lst[i] ? ++acc : acc, 0);
  }
  return lst;
}
console.log(numberOfSmallerElem2(lst));

function numberOfSmallerElem3(lst) {
  const ret = [];
  for (let i = 0, len = lst.length; i < len - 1; i++) {
    const reference = lst[i];
    let counter = 0;
    for (let j = i + 1; j < len; j++) {
      if(lst[j] < reference) { counter++; }
    }
    ret.push(counter);
  }
  ret.push(0);

  return ret;
}
console.log(numberOfSmallerElem3(lst));
\$\endgroup\$
2
\$\begingroup\$

Performance

The posted implementations are quadratic. A log-linear solution exists. Here's a hint:

What if you insert values from right to left into a sorted list?

Avoid mutations in functional implementations

Can you spot the mutation on this line?

const numberOfSmallerElem = lst => lst.map((x,i) => lst.slice(i + 1).reduce((acc,y) => y < x ? acc++ : acc, 0));    

It's actually not easy to spot it when the line is so long! I suggest to break it up, for readability. And then eliminate the mutation.

Replace acc++ with acc + 1

\$\endgroup\$
  • \$\begingroup\$ So in functional programming you don't do increment/decrement, i.e. a++/a--? \$\endgroup\$ – thadeuszlay Apr 11 at 14:40

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.