Find the repeated item in an array using TypeScript
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.
[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.