CODEWITHSUNDEEP
javascriptarrays
Zhurovich
Zhurovich

Reputation: 75

How to group the "closest" numbers in an array using javascript

I have an array of numbers sorted in ascending order. How to group the "closest" numbers (where the difference between the numbers is less than 5, for example)? So out of [1, 4, 5, 23, 40, 55, 56, 100, 234] I want to get [[1, 4, 5], 23, 40, [55, 56], 100, 234]

Upvotes: 1

Views: 1132

Answers (5)

Redu
Redu

Reputation: 26171

This is a good question...

Though my answer is slightly convoluted, for experimental purposes you can also do like this...

var data = [1, 4, 5, 23, 40, 55, 56, 100, 234],
  result = data.reduce((p,c) => p.length ? p[p.length-1].length ? c-p[p.length-1][p[p.length-1].length-1] < 5 ? (p[p.length-1].push(c),p)
                                                                                                              : (p.push(c),p)
                                                                : c-p[p.length-1] < 5 ? (p[p.length-1] = [p[p.length-1],c],p)
                                                                                      : (p.push(c),p)
                                         : c-p < 5 ? [[p].concat(c)]
                                                   : [p,c]);
console.log(JSON.stringify(result));

I think it's pretty efficient too.

Ok so let's try something funny... We will feed this algorithm with an array of 1,000,000 random items among 1 ~ 5,000,000 in sorted order and measure how long it takes to group them for a diff < 5.

var data = Array(1000000).fill()
                         .map(_ => ~~(Math.random()*5000000)+1)
                         .sort((a,b) => a-b),
  result = [];
console.time("grouping");
  result = data.reduce((p,c) => p.length ? p[p.length-1].length ? c-p[p.length-1][p[p.length-1].length-1] < 5 ? (p[p.length-1].push(c),p)
                                                                                                              : (p.push(c),p)
                                                                : c-p[p.length-1] < 5 ? (p[p.length-1] = [p[p.length-1],c],p)
                                                                                      : (p.push(c),p)
                                         : c-p < 5 ? [[p].concat(c)]
                                                   : [p,c]);
console.timeEnd("grouping");
console.log(result.length);

Like ~200ms in average. Seems cool..!

Upvotes: 1

Pranav C Balan
Pranav C Balan

Reputation: 115232

Use Array#reduce method with an empty array as the initial value where update the array by checking the last element.

var data = [1, 4, 5, 23, 40, 55, 56, 100, 234];

var res = data.reduce(function(arr, e) {
  // cache last element index
  var i = arr.length - 1;
  // check array exist atleast one element
  if (i > -1) {
    // check last element is array
    if (Array.isArray(arr[i])) {
      // compare last element in array and current element is adjacent
      // if yes push into that array otherwise push into main array
      e - arr[i][arr[i].length - 1] < 5 ? arr[i].push(e) : arr.push(e);
      // if last element is not an array
    } else {
      // if last element and current element is adjacent
      // update last element with an array or just push as usual
      e - arr[i] < 5 ? arr[i] = [arr[i], e] : arr.push(e);
    }
    // if array is empty
  } else
  // simply push the element
    arr.push(e);
  // retuen the array reference
  return arr;
  // set initial value as an epty array
}, [])

console.log(res);

Upvotes: 3

Nenad Vracar
Nenad Vracar

Reputation: 122057

You can use reduce and check last element added to add to last array or insert new one, and when you get to last element of data you use map to remove arrays with one element.

var data = [1, 4, 5, 23, 40, 55, 56, 100, 234];

var result = data.reduce(function(r, e, i) {
  if (i != 0) {
    (e - data[i - 1] < 5) ? r[r.length - 1].push(e): r.push([e])
  } else {
    r.push([e])
  }
  if (i == data.length - 1) r = r.map(e => e.length == 1 ? e[0] : e)
  return r;
}, [])

console.log(result)

Upvotes: 2

Jonas Wilms
Jonas Wilms

Reputation: 138327

What about another (may shorter)reduce:

 newarray=array.reduce((newarray,number)=>{
   var last=newarray.pop()||[];
      if(last.every(elem=>elem+6>number)){
       last.push(number);
       newarray.push(last);
       return newarray;
      }
       newarray.push(last);
       newarray.push([number]);
       return newarray;
      },[]);

Upvotes: 2

Nina Scholz
Nina Scholz

Reputation: 386654

You could check the predecessor and if in range add to array.

var data = [1, 4, 5, 23, 40, 55, 56, 100, 234],
    result = data.reduce(function (r, a, i, aa) {
        if (a - aa[i - 1] < 5) {
            if (!Array.isArray(r[r.length - 1])) {
                r[r.length - 1] = [r[r.length - 1]];
            }
            r[r.length - 1].push(a);
            return r;
        }
        r.push(a);
        return r;
    }, []);

console.log(result); // [[1, 4, 5], 23, 40, [55, 56], 100, 234]

Upvotes: 7

Related Questions