Slice an array of arrays by the first 3 unique values of one of them

Question

I have an array:

var items = [[1,1,2,2,3,3,4,4,5,5],[0,0,0,1,0,1,0,1,0,1]];

Put another way, I want to loop through the elements of items[0] and items[1] and collect all the elements until I've found three unique values for items[0].

The output I want is:

output = [[1,1,2,2,3,3],[0,0,0,1,0,1]];

And what happens to `items[1]` ? It just have 2 distinct elements .. I think you just truncated it to the same length of `items[0]`. — Ahmad Ibrahim, Jun 23 '15 at 23:02
Yes. I want to truncate items[1]. Basically I have a x and y data for plotting and I want to only plot the pairs for the first 3 unique values of x. — Anton, Jun 23 '15 at 23:03
Will `items` ever contain more than two arrays? If it does do you want to do the same thing to the rest of them or do you always want to just process the first two items? — Useless Code, Jun 23 '15 at 23:04
It will never have more than 3 arrays (x, y, and z). I only care about the unique values of x — Anton, Jun 23 '15 at 23:04
@Anton I put my answer, but not if be correct but gives the result, maybe I'm not understanding the question correctly, you could give another example? — Walter Chapilliquen - wZVanG, Jun 23 '15 at 23:11
Why have separate arrays for x and y? wouldnt this make more sense `[[1,0], [1,0], [2,0], [2,1], [3,0]....]` ? With that structure, this wouldn't be an issue. It would also make it easier to compare both the `x` and `y` coordinates. — Jan, Jun 23 '15 at 23:42

score 2 · Accepted Answer · edited May 23 '17 at 12:29

If I understand you correctly, then the following will do what you want.

function threeDistincts(items) {
    var distincts = 0, inArr = false;
    for (var i = 0; i < items[0].length; i++) {
        inArr = false;
        for (var j = 0; j < i; j++) {
            if (items[0][j] === items[0][i]) {
                inArr = true;
                break;
            }
        }
        if (!inArr) distincts++;
        if (distincts === 4) break;
    }
    items[0].length = items[1].length = i;
}

Call it like:

var items = [[1,1,2,2,3,3,3,4,5,5],[0,0,0,1,0,1,0,1,0,1]];

threeDistincts(items);

// items = [[1,1,2,2,3,3],[0,0,0,1,0,1]];

Working Fiddle.

Another version of this function, using indexOf (as DTing suggested), will limit the inner loop (in the original function) to the distinct elements only, but considering the high complexity of Array.indexOf and Array.push implementation, better performance is not guaranteed.

function threeDistincts(items) {
    var arr = [];
    for (var i = 0; i < items[0].length; i++) {
        if (arr.indexOf(items[0][i]) === -1) arr.push(items[0][i]);
        if (arr.length === 4) break;
    }
    items[0].length = items[1].length = i;
}

This is basically using `indexOf` but coded with a for loop. O(n^2) time complexity. — dting, Jun 24 '15 at 00:52
@DTing note that I'm not searching the whole array, I'm just searching up to a certain index (`for (...; j < i; ...)`), if you want to use `indexOf` you will have to create a sub-array, which will _possibly_ add greater overhead. — Ahmad Ibrahim, Jun 24 '15 at 01:02
In the worst case, even optimizing the for loop condition for elements less than i, you get n^2 time. For example `1,2,.....,2,3,......,3,4` The nested for loop will have to look through all the 2's before finding the 3's . — dting, Jun 24 '15 at 05:21

Noah Freitas · Answer 2 · 2015-06-23T23:52:20.393

Using the newer Set and Array.prototype.findIndex JavaScript features, which can be polyfilled via es6-shim for older browsers.

// limitTo3DistinctFromFirst :: [[a], [b]] -> [[a], [b]]
function limitTo3DistinctFromFirst(items) {
    var uniques       = new Set(),
        indexOfFourth = items[0].findIndex(fourthUnique);

    return items.map(sliceToFourth);

    // fourthUnique :: a -> Boolean
    function fourthUnique(el) {
        if (uniques.has(el)) return false;
        uniques.add(el);
        return uniques.size === 4;
    }

    // sliceToFourth :: [a] -> [a]
    function sliceToFourth(a) {
        return a.slice(0, indexOfFourth);
    }
}

That's purdy. Unsupported, but purdy. – Jan Jun 23 '15 at 23:51 — Jan, Jun 23 '15 at 23:51

dting · Answer 3 · 2015-06-23T23:18:09.877

You can use an object to track how many unique items you have seen if your objects are hashable:

If you want to stop after you add a third unique value:

var items = [[1,1,2,2,3,3,4,4,5,5],[0,0,0,1,0,1,0,1,0,1]];

function solve(items) {
  var obj = Object.create(null);
  var seen = 0;
  var i = -1;
  while (++i < items[0].length && seen < 3) {
    var element = items[0][i];
    if (element in obj) continue;
    obj[element] = true;
    seen++;
  }
  return [items[0].slice(0,i), items[1].slice(0,i)];
};

document.getElementById('result').innerHTML = JSON.stringify(solve(items));

<pre id="result"></pre>

If you want to break out of the loop when the 4th unique value is seen, you can do it like this:

var items = [[1,1,2,2,3,3,4,4,5,5],[0,0,0,1,0,1,0,1,0,1]];

function solve(items) {
  var obj = Object.create(null);
  var seen = 0;
  var i = -1;
  while (++i < items[0].length && seen < 4) {
    var element = items[0][i];
    if (element in obj) continue;
    obj[element] = true;
    seen++;
  }
  return [items[0].slice(0,i-1), items[1].slice(0,i-1)];
};

document.getElementById('result').innerHTML = JSON.stringify(solve(items));

<pre id="result"></pre>

Thomas Eschemann · Answer 4 · 2015-06-23T23:53:51.547

You could use an object as a set to keep track of the number of unique values already selected. This has the benefit of preventing unnecessary iterations.

var func = function (data) {
  var selectedValues = {};
  var sliceIndex = 0;

  while (Object.keys(selectedValues).length < 3 && sliceIndex < data[0].length) {
    selectedValues[data[0][sliceIndex]] = true;
    sliceIndex++;
  }

  return data.map(function (axis) {
    return axis.slice(0, sliceIndex);
  });
};

console.log(func([[1,1,2,2,3,3,4,4,5,5],[0,0,0,1,0,1,0,1,0,1]]));

Slice an array of arrays by the first 3 unique values of one of them

4 Answers4