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));
asked Apr 10, 2019 at 8:48
\$\endgroup\$

1 Answer 1

3
\$\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

answered Apr 11, 2019 at 8:05
\$\endgroup\$
1
  • \$\begingroup\$ So in functional programming you don't do increment/decrement, i.e. a++/a--? \$\endgroup\$ Commented Apr 11, 2019 at 14:40

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.