Join egghead, unlock knowledge.

Want more egghead? It's 45% off for a limited time only!

This lesson is for members. Join us? Get access to all 3,000+ tutorials + a community with expert developers around the world.

Unlock All Content for 45% Off

Already subscribed? Sign In

Save 45% for a limited time.

Get access to all courses and lessons on egghead today.

Autoplay

    Find the repeated item in an array using TypeScript

    Basarat Ali SyedBasarat Ali Syed

    Say you have an array that has at least one item repeated. How would you find the repeated item. This is a question commonly presented to beginner developers. Here we discuss the elegant solution to this problem.

    typescriptTypeScript
    Code

    Code

    Become a Member to view code

    You must be a Member to view code

    Access all courses and lessons, track your progress, gain confidence and expertise.

    Become a Member
    and unlock code for this lesson
    Transcript

    Transcript

    00:01 We start off by creating a function which takes an array of type t items, and returns a repeated item, if any. Within the function, we will throw an error if no item repetition is found.

    00:18 Intuitively, we can check item repetition by iterating through all the items of the array one by one, and for each item, checking it against any items that appear further in the array. We'll start the second iteration from add plus one.

    00:35 If the current item and some item on the right of it matches, we have found a duplicate and we can return it. This implementation does work fine. However, due to the two loops, the worst-case runtime is of the order n^2, where n is the length of the array.

    00:54 We can do better by using a data structure designed for checking object uniqueness. Obviously, we're going to use a set. We start off by creating a set for items of type t. We loop through each item in the array. If an item of the same value already exists in the set, we have found a duplicate, and we return it.

    01:20 Otherwise, we add this item to the set and continue. Once the loop completes, we throw the same as before. Since we only loop through the items in the array once, doing constant work in each loop thanks to the set data structure, the runtime now falls to the order of n, where n is the length of the array.

    Discuss

    Discuss