Check if duplicate array pairs exist using underscore only

Question

I am wondering how I can check if a duplicate pair of values in an array exist as part of a larger array in javascript. You can see there is a duplicate pair of [1,2] - so the function should just return true. i.e

var arr = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12], [13,14], [1,2]]

I have tried using this logic which gives me a clean array and a "true"

var unique = [];
var done = []; var dup = false;
for(var x = 0; x < arr.length; x++) {
    var myStr = arr[x].toString();

    if(done.indexOf(myStr) != -1) {
        // val already exist, ignore
        dup = true;
        continue;
    }

    done.push(myStr);
    unique.push(arr[x]);
}

But I was wondering if there is something more elegant using Underscore ?

score 5 · Accepted Answer · edited May 23 '17 at 11:44

5

The shortest way would be to use _.uniq and JSON.stringify:

function unique(arr) {
    return _.uniq(arr, JSON.stringify).length === arr.length;
}

But that doesn't short-circuit, so it's somewhat slow compared to the other ways you could do it. Tomalak's second function should be faster.

edited May 23 '17 at 11:44

Community

1
1

answered May 26 '13 at 17:52

Blender

289,723
53
439
496

`JSON.stringify` is a lot nicer than `.toString()` or `.join()`. +1 PS: Hah, we implemented the same pure JS solution... :) I'd just be careful with the use of `in`. `hasOwnProperty()` returns `false` for the string `"length"`, `in` would return `true`. – Tomalak May 26 '13 at 18:00
1

The second solution doesn't actually work if an array contains strings that look like joined arrays like `"1,2"` etc. Remember, object keys are always strings! `stringify` is much better as it carries type and uses it for comparisons. – georg May 26 '13 at 18:10
@thg435: Well, if I were to fix it, then you'd basically get [Tomalak's](http://stackoverflow.com/a/16762040/464744) answer ;) – Blender May 26 '13 at 18:11
@Blender: he's making the same mistake: `containsDuplicates([[1,2], "1,2"])` returns true. – georg May 26 '13 at 18:13
@thg435: From what I understood, OP is just working on arrays of arrays of numbers, so it would work in his case. But yes, that would be a problem if there were mixed data types. – Blender May 26 '13 at 18:14
@thg435 Yes, I was making assumptions about the input. Plus I did not think of JSON.stringify. I shall fix that. – Tomalak May 26 '13 at 18:14
yeah the inputs will be integers - not strings. But it would be great to account for both for completeness :) – Andy May 26 '13 at 18:23
1

@Andy: Yep. If the array without duplicates has the same number of elements as the array with duplicates, then no duplicates were ever there. – Blender May 26 '13 at 18:28
also is there any way to modify it so I can check for a specific duplicate ? – Andy May 26 '13 at 18:40
@Andy: What's a specific duplicate? – Blender May 26 '13 at 18:41
sorry - so I mean - I am pushing new values into the array. What I wanted to do was check if that new `[1,2]` value I just pushed already exists and skip it ? the value would still remain in the array however – Andy May 26 '13 at 18:42
@Andy: Keep a dictionary of already-present elements (similar to what Tomalak is doing) and use that. – Blender May 26 '13 at 18:44
@Blender - thanks for the response. Bit unsure how to just get a result for the most recent ? i.e. like `containsDuplicates(arr, newPair)` - which is like `containsDuplicates(arr, [5,6])` ? appreciate any help – Andy May 26 '13 at 19:10
@Andy: you're looking for Sets. See http://stackoverflow.com/q/7958292/989121 etc – georg May 26 '13 at 19:55
@thg435 - is that a bit overkill ? what about something like - http://jsbin.com/oreval/5/edit ? – Andy May 26 '13 at 20:28

Tomalak · Answer 2 · 2013-05-26T18:18:59.667

2

Well, uniq seems like a good fit

function containsDuplicates(arr) {
  return arr.length !== _.uniq(arr, function (item) { return item.toString(); }).length;
}

You should use Blender's version of this function. It's shorter and safer.

BTW, your code should look more like this:

function containsDuplicates(arr) {
    var index = {}, i, str;

    for(i = 0; i < arr.length; i++) {
        // you could use arr[i].toString() here, but JSON.stringify()
        // is a lot safer because it cannot create ambiguous output.
        str = JSON.stringify(arr[i]);
        if (index.hasOwnProperty(str)) {
            return true;
        } else {
            index[str] = true;
        }
    }

    return false;
}

Note that this is probably more efficient than the underscore one-liner.

edited May 26 '13 at 18:18

answered May 26 '13 at 17:51

Tomalak

332,285
67
532
628

@WillemD'haeseleer I'm pretty sure it works. How did you test it? – Tomalak May 26 '13 at 17:55
in my browser, seems like Blender fixed it for you now – Willem D'Haeseleer May 26 '13 at 17:56
@Willem Darn copy/paste mistakes. Yes, that was it. – Tomalak May 26 '13 at 17:59
@Tomalak - thanks for the response. Is there a way to check whether the latest pair pushed to the array is a duplicate ? Not just whether "any duplicate" exists ? i.e. like `containsDuplicates(arr, newPair)` - which is like `containsDuplicates(arr, [5,6])` – Andy May 26 '13 at 18:54
@Andy If you ask me like this... yes, there is a way to do this. :) – Tomalak May 26 '13 at 20:57
@Tomalak - apologies if did something wrong :) I ended up trying to do something like this - http://jsbin.com/unasem/2/edit. Its sort of messy but it works. Would REALLY TOTALLY appreciate any help! Thanks! – Andy May 26 '13 at 22:57
@Andy Well, that's messy indeed. Can you explain what you are trying to do? Seems like you actually want something like `arr.pushIfNotExists(value)`, could that be? – Tomalak May 27 '13 at 09:14
@Tomalak - actually all I am trying to do is to return whether the pair of `[1,2]` exists in an array of arrays. Its difficult as there isnt any underscore etc function to do this where its an array of arrays ? http://jsbin.com/unasem/4/edit - this works but isnt great – Andy May 27 '13 at 20:07

score 2 · Answer 3 · answered May 26 '13 at 18:30

Although stringify is the answer most of the time, it still has its issues, for example {"x":1,"y":2} and {"y":2,"x":1} are considered different. If you need a 100% accurate comparison, there's no other way as to store already processed objects and deep compare them (luckily, underscore provides an utility for this).

uniq2 = function(xs) {
    return _.reduce(xs, function(result, x) {
        if(!_.any(result, _.partial(_.isEqual, x)))
            result.push(x);
        return result;
    }, []);
}

Test:

var arr = [[1,2], [3,4], "1,2", "[1,2]", [1,2], {x:1,y:2}, {y:2,x:1}]
console.log(uniq2(arr))
// [[1,2],[3,4],"1,2","[1,2]",{"x":1,"y":2}]

This is going to be quadratic in the worst case, but there's no other way.

Check if duplicate array pairs exist using underscore only

3 Answers3

Linked