Find the Repeated Item

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

If you already have a subscription, you can sign in.

Find the Repeated Item

Subscription Required

You must have an active subscription to access this content.
If you already have a subscription, you can sign in.

Problem

/**
* Returns the first repeated item from an array if any
*/
export function repeatedItem<T>(array: T[]) {

}

Solution

export type RepeatedItemResult<T> =
| { type: 'found', item: T }
| { type: 'not-found' };

/**
* Returns the first repeated item from an array if any
*/
export function repeatedItem<T>(array: T[]): RepeatedItemResult<T> {
const set = new Set<T>();
for (const item of array) {
if (set.has(item)) return { type: 'found', item };
else set.add(item);
}
return { type: 'not-found' };
}

Transcript

00:00 Today's coding interview question is something

00:02 that is quite easy to solve naively

00:04 and the efficient solution also serves

00:06 as a nice introduction

00:07 to a really used built-in JavaScript data structure.

00:11 So let's go now.

00:13 The problem that we have to solve today is

00:15 to find the repeated item within a given input array.

00:19 However, before we look at an actual solution

00:22 to this problem, let's discuss what we are going

00:24 to return if we don't find a repeated item.

00:28 One solution is to throw an error in case no

00:30 duplicates are found.

00:32 Now this is not ideal because exceptions should be

00:35 for exceptional cases.

00:36 You don't want your functions throwing errors just

00:39 because you didn't find something.

00:42 When you write code like this,

00:43 it normally results in the colors of your functions having

00:46 to write some additional code just to make sure

00:48 that you're not going to throw an error on them.

00:50 Traditionally, an alternative approach is

00:53 to return a special value like now.

00:55 However, this is not ideal either.

00:58 For example, the item that you actually find

01:01 that is repeated might be no.

01:03 In such a scenario, no can mean two things.

01:05 It can mean not found, or it can mean I found two nels.

01:09 Fortunately, the solution is pretty simple.

01:11 We come up with this return type, which has a member

01:14 that can signify the nature of the return object.

01:17 If the value of the type member in the return object points

01:20 to the string found, it means

01:22 that we have found a duplicate item

01:24 and the item is going to be contained in the item property.

01:27 Otherwise, the type member

01:28 of the return object will have the string not found.

01:33 With that out of the way, we can write a needs scaffold

01:35 for the problem that we are trying to solve.

01:38 We want to find the repeated item within an array of items

01:41 of type T, and we will return the repeated item

01:44 result of type T.

01:46 Now, in case we don't find anything,

01:48 we will return this object containing the type member

01:50 pointing to the string not found.

01:53 Now to start off for a solution, we are going

01:55 to use a naive approach because

01:57 after all, some solution is better than no solution.

02:01 We go through the items in the array

02:03 and for each item we start another loop at I plus one

02:07 and search all the way till the end of the array to see if

02:10 that item appears again,

02:12 anywhere further on within the array.

02:14 If at any point the JTH item turns out to be equal

02:17 to the ITH item, we return an object

02:20 with the type saying found

02:21 and the item member containing the ITH item.

02:24 Now, the runtime for this particular algorithm

02:26 to find the repeated item is going to be O of N square

02:29 because we are going to be looping

02:31 through the input array twice first for I and then for J.

02:36 Now, the better implementation is going to loop

02:38 through the input array only once,

02:40 and we are going to use a data structure

02:42 that is especially designed for checking object uniqueness.

02:47 And if you guessed it gurus to you, we are going

02:49 to use the set data structure.

02:52 We simply look through the input array once,

02:55 and if we already have seen that item

02:57 before, because the set

02:58 Has that item and congratulations,

03:01 we have found a duplicate

03:02 and we are going to return type found with the item added.

03:05 Otherwise, we are going to add this item to the set

03:08 and continue the loop.

03:09 And if that item ever appears again within the array set out

03:12 has will be true and we would have found a duplicate.

03:16 According interview questions go.

03:18 This one is pretty easy to solve if you are familiar

03:21 with the set data structure

03:22 that is built in within JavaScript.

03:24 This is something that separates a beginning developer from

03:27 someone who's prepared

03:28 for algorithm coding interview questions, for example,

03:30 by watching videos like this.