Enter Your Email Address to Watch This Lesson

Your link to unlock this lesson will be sent to this email address.

Unlock this lesson and all 1083 of the free egghead.io lessons, plus get TypeScript content delivered directly to your inbox!



Existing egghead members will not see this. Sign in.

Find the repeated item in an array using TypeScript

1:44 TypeScript lesson by

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.

Get the Code Now
click to level up

egghead.io comment guidelines

Avatar
egghead.io

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.

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.

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.

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.

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.

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.

HEY, QUICK QUESTION!
Joel's Head
Why are we asking?