array

Find Duplicate Element in JavaScript Array

1
2
3
4
5
6
7
function uniq(l) {
  return l.filter(function (e, i) { return l.indexOf(e) === i; });
}
function findDup(l) {
  return uniq(l.filter(function (e, i) { return l.indexOf(e) !== i; }));
}

Example:

1
2
> findDup([1, 2, 3, 4, 2, 5, 1, 2]);
< [2, 1]

Efficient Representation of a Sparse Array in JavaScript

I’m using an array to represent ranges of numbers. For example, in this array,

1
[1, 2, 3, 4, 15, 16, 17, 18]

there are two sequences of consequitive numbers: 1-4 and 15-18. In order to save space when serializing this array, it can be represented as ranges of numbers. For example:

1
[ [1, 4], [15, 18] ]

This function takes in an array of numbers, and returns an array of ranges:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function sparsify(l) {
  var i, j, k;
  var ranges = []; // [ [from, to], [from, to], ... ]
  function insertNum(n) {
    for (j = 0; j < ranges.length; j++) {
      if (ranges[j][0] <= n && n <= ranges[j][1]) return; // already in a range
      if (n === ranges[j][0] - 1)      // immediately before a range
        ranges[j][0] = n;
      else if (n === ranges[j][1] + 1) // immediately after a range
        ranges[j][1] = n;
      else
        continue;
      for (k = 0; k < ranges.length; k++) { // merge ranges
        if (j === k) continue;
        // do ranges j and k overlap?
        if ( (ranges[j][0] <= ranges[k][0] && ranges[k][0] <= ranges[j][1] + 1) ||
             (ranges[j][0] - 1 <= ranges[k][1] && ranges[k][1] <= ranges[j][1])) {
          ranges[j] = [Math.min(ranges[j][0], ranges[k][0]), Math.max(ranges[j][1], ranges[k][1])];
          ranges.splice(k, 1);
          break;
        }
      }
      return;
    }
    ranges.push([n, n]);     // not found; add new range
  }
  for (i = 0; i < l.length; i++)
    insertNum(l[i]);
  return ranges;
}