loading...

Daily Challenge #256 - How Many Are Smaller Than I?

thepracticaldev profile image dev.to staff ・1 min read

Write function smaller(arr) that given an array arr, you have to return the amount of numbers that are smaller to the right of that number in the index.

For example:
smaller([5, 4, 3, 2, 1]) === [4, 3, 2, 1, 0]
smaller([1, 2, 0]) === [1, 1, 0]

Tests:
smaller([5, 4, 3, 2, 1])
smaller([1, 2, 3])
smaller([1, 1, -1, 0, 0])
smaller([5, 4, 7, 9, 2, 4, 4, 5, 6])

Good luck!


This challenge comes from joh_pot on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
aminnairi profile image
Amin

TypeScript

const smaller = (items: number[]): Uint32Array => {
    const length: number = items.length;
    const output: Uint32Array = new Uint32Array(length);

    for (let current: number = 0; current < length; current++) {
        output[current] = 0;

        for (let next: number = current + 1; next < length; next++) {
            if (items[next] < items[current]) {
                output[current]++;
            }
        }
    }

    return output;
};
Collapse
vidit1999 profile image
Vidit Sarkar

Here is a C++ solution,

vector<int> smaller(vector<int> arr){
    map<int, int> m;
    vector<int> ans(arr.size(), 0);

    for(int i = arr.size()-1; i >= 0; i--){
        auto it = m.insert({arr[i], m[arr[i]]++});

        for(auto itr = m.begin(); itr != it.first; itr++) ans[i] += (*itr).second;
    }

    return ans;
}

Test cases,

smaller([5, 4, 3, 2, 1]) => [4, 3, 2, 1, 0]
smaller([1, 2, 0]) => [1, 1, 0]
smaller([1, 2, 3]) => [0, 0, 0]
smaller([1, 1, -1, 0, 0]) => [3, 3, 0, 0, 0]
smaller([5, 4, 7, 9, 2, 4, 4, 5, 6]) => [4, 1, 5, 5, 0, 0, 0, 0, 0]
Collapse
davejs profile image
David Leger
const smaller = (arr: number[]): number[] => {
  // loop over items
  return arr.map((item, i) => {
    // get array of remaining items
    const rest = arr.slice(i + 1, arr.length);

    // filter for items less than the current item
    const lessThan = rest.filter(curr => curr < item);

    // count the items less than
    return lessThan.length;
  })
}
Collapse
jpantunes profile image
JP Antunes

Simple JS solution.

const smaller = arr => arr.reduce((acc, val, idx) => {
    acc[idx] = arr.filter((e, i) => e < val && i > idx).length;
    return acc;
},[]);
Collapse
timon profile image
Timon van Spronsen
function smaller(arr) {
  return arr.map((x, i) => arr.slice(i).filter((y) => y < x).length);
}
Collapse
miketalbot profile image
Mike Talbot

const smaller = arr => arr.reduce((c,a,i)=>{
   for(let j =0; j < i; j++) { 
       c[j] = (c[j] || 0) + arr[j] > a ? 1 : 0 
   }
   return c
}, [])

Collapse
saswat01 profile image
saswat

This is a trivial python solution.