3

Hi Currently I have an array like this in my typescript code . How can i check if there is an item in my array appears twice. I would like create function the will return true or false if the array passed contains a duplicate element.

  let tagonTypes: Array<string> = [];
  tagonTypes.push("NTM");
  tagonTypes.push("MCD");

in the above array there is no duplicate so the function should return false.

  let tagonTypes: Array<string> = [];
  tagonTypes.push("NTM");
  tagonTypes.push("NTM");

In the above array my function should return true because "NTM" is repeated.

any idea how my function looks like

thank you

3
  • I'm a little confused, are you checking post-update to the array if you have duplicates (now)? Or just trying to prevent duplicates? Like this? jsfiddle.net/n3du986r/1 Commented Nov 7, 2019 at 17:28
  • The requirement is simply to write a function which returns true if the array contains duplicates and false if it doesn't. The question doesn't ask how to prevent duplicates from being added. Commented Nov 7, 2019 at 17:59
  • @kaya3 I think I can handle myself, thanks. Commented Nov 7, 2019 at 19:21

7 Answers 7

3

You can use set size if all you need is to check if there has been duplicates added:

function hasDuplicates<T>(arr: T[]): boolean {
  return new Set(arr).size < arr.length;
}

hasDuplicates(["A", "A"]) // true
hasDuplicates(["A", "B"]) // false

You can also use the proxy object to know when duplicate is added as they get added to the array:

const myArray1 = ["a", "b"];

const myArrayProxy1 = new Proxy(myArray1, {
  set: (target, property, value) => {
    const exits = target.includes(value);
    if (exits) {
      console.log(`Duplicate index ${property.toString()}, value: ${value}`);
    }
    return true;
  }
});

myArrayProxy1.push("a", "a", "b", "c");
// Prints:
// Duplicate index 2, value: a
// Duplicate index 3, value: a
// Duplicate index 4, value: b

If you do want to want to be proactive and just work with your array without it having duplicates you can override the setting logic:

const myArray2 = ["a", "b"];

const myArrayProxy2 = new Proxy(myArray2, {
  get: (target, property) => {
    return Reflect.get(target.filter(Boolean), property);
  },
  set: (target, property, value) => {
    const exits = target.includes(value);
    return exits ? true : Reflect.set(target, property, value);
  }
});

myArrayProxy2.push("a", "a", "b", "c");
console.log([...myArrayProxy2]); // - Prints: ["a", "b", "c"]
Sign up to request clarification or add additional context in comments.

4 Comments

This works, but doesn't short-circuit when a duplicate is found early on.
This is a very strange way to solve the problem when you could just write a loop, and note that you are creating a new Set instance every time a value is added to the array.
Array.includes requires scanning the whole array, so the solution is still O(n^2). This is a simple problem and you are making it far too complicated.
No, your solution still doesn't actually short-circuit when a duplicate is found early on; in principle it's the same as your original attempt except you have invented your own (rather inefficient) Set data structure.
2

Here is a method to check if there are duplicates in a simple indexed array.

const hasDuplicates = (set, items = []) => {
    return set.reduce((duplicates, item) => {
        return (duplicates || items.includes(item))
            || items.push(item) && false
    }, false)
}

https://jsfiddle.net/cotpgkyd/1/

Here's another method that can reduce a list to just it's non-duplicates.

const unique = (set, item) => {
    return (set.includes(item) || set.push(item)) && set
}

Called as either a coalesce or reduction:

var myList = []

myList = unique(myList, 'a')
myList = unique(myList, 'b')
myList = unique(myList, 'c')
myList = unique(myList, 'b')
myList = unique(myList, 'c')
myList = unique(myList, 'c')

console.log(myList)                           // ["a", "b", "c"]

var myOtherList = ['a','b','c','b',];

console.log(myOtherList.reduce(unique, []))   // ["a", "b", "c"]

https://jsfiddle.net/pnt9gaq6/

2 Comments

Nice. This is the good stuff :) why do you prefer index of to includes?
@AliHabibzadeh Force of habit. Updated to use includes().
1

Insert the elements into a Set, and use the Set.has method to test if each value is already present before you insert it:

function hasDuplicates<T>(array: Array<T>): boolean {
    const asSet: Set<T> = new Set();
    for(let x of array) {
        if(asSet.has(x)) { return true; }
        asSet.add(x);
    }
    return false;
}

This runs in O(n) time because testing if the set contains x is O(1). The loop stops looking at more elements from the array as soon as a duplicate value is detected.

6 Comments

An array that has the possibility of having duplicates needs to be checked every time an item is added with your function, meaning a new set is created every time also.
No, it is straightforward to verify that this function creates one set, not one set per array-element. The new Set() constructor is called outside of the loop.
But hasDuplicates has to be called everytime the array is different which is every time is has a new item
The OP asked for a function which tests whether an array contains duplicates. That's what this is. The OP didn't ask for an array which duplicates can't be added to.
Just for fun I tested this code against just using an object and for loop and this is always twice as slow as using an plain object (~2000ms vs ~1000ms on 8000 elements). Any benefit to using that construct here? Benchmark: jsben.ch/IWaDL
|
1

Based on the solution here: https://stackoverflow.com/a/49215411/8676371

The method: duplicate will tell you if your array has duplicate elements.


let strArray = ["q", "w", "w", "e", "i", "u", "r"];

// Add this:
Array.prototype.duplicate = function () {
    return this.some((item, index) => this.indexOf(item) != index);
}

// Use it like this:
var dup = strArray.duplicate();

console.log(dup); // Outputs: true.

Comments

1

Any problem just going vanilla? Of course adding typescript stuff to the below but I don't get the relevance of TS to the question. Not sure the benefit of using more constructs like a Set when this is trivial. I'd be interested to know if I'm missing something but I'd just use an object to efficiently track elements as you loop and check for duplicates - as soon as you find one, return true.

One idea I was thinking of was if in some cases sorting the array first may help performance for large arrays and find duplicates faster but that would have its own overhead...

EDIT: If anyone is interested I tested this against using a Set and going plain vanilla is consistently 2X faster. http://jsben.ch/IWaDL

var array = ['NOM', 'NOM', 'NO', 'YES', 'DUP', 'DUP'];
var arrayTwo = ['NOM', 'NO', 'YES', 'DUP'];

var hasDuplicates = function (arr) {
  var obj = {};
  for (var i = 0; i < arr.length; i++) {
    if (obj[arr[i]])
      return true;
    obj[arr[i]] = 1;
  }
  return false;
};

console.log(hasDuplicates(array));
console.log(hasDuplicates(arrayTwo));

Comments

1

Create a Set ( a unique collection) out of all elements of the array and compare the lengths of the original array and the unique set that you created. if the number of elements in the array and the newly created set is not equals, that means you have duplicates.

function hasDuplicateElements(elements:any[] ):boolean {
   // check the length of array with size of the Set created with array
   return elements.length != new Set(elements).size;
 
}

let arrayDup=[5,7,8,"Any",7]

let arrayUnique=[5,7,8,"A","Some",1]

// this returns true as arrayDup contains duplicate entities
hasDuplicateElements(arrayDup);

// this returns false as arrayUnique has uniqe entities.
hasDuplicateElements(arrayUnique);

Comments

0

Hi all there are 3 solutions. 1. Using Set.

copy the array to a typescript set. On comparing the length of the set and array if they differ it means duplicate is there .

  let tagonTypes: Array<string> = [];
  tagonTypes.push("NTM");
  tagonTypes.push("MCD");

  let tagonTypesSet = new Set(tagonTypes)

tagonTypes.length!= tagonTypesSet.length // duplicates were present in the tagonTypes array and eliminated from the set.

  1. use a filter .

    let tagonTypes: Array = []; tagonTypes.push("NTM"); tagonTypes.push("MCD");

      tagonTypes.filter( (item,index ) => {
        return tagonTypes.indexOf(item) === index
       });
    

    this will filter out the duplicates . the duplicates are where the index doesnt match the indexOf . so in those cases, the condition will be false and wont be included in the filtered array.

the filter array size then we compare with real one . if size difference is there it means duplicates are present.

3) Using reduce

The reduce method is used to reduce the elements of the array and combine them into a final array based on some reducer function that you pass. In this case, our reducer function is checking if our final array contains the item. If it doesn’t, push that item into our final array. Otherwise, skip that element and return just our final array as is (essentially skipping over that element). Reduce is always a bit more tricky to understand, so let’s also step into each case and see the output:

   let tagonTypes: Array<string> = [];
      tagonTypes.push("NTM");
      tagonTypes.push("MCD");

tagonTypes.reduce( (unique,item ) => {
return unique.includes(item) ? unique : [...unique,item]
},[]);

again compare the length of the array return by the reduce function and compare with length of the original array.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.