## Optimizing Array Search in JavaScript: Using `Set`

for Efficient Lookups

When working with large datasets in JavaScript, efficiently searching for
elements across two arrays can make a significant difference in performance. A
common use case is finding the first common element between two large arrays.
Without optimization, this can become a computationally expensive operation.
Fortunately, using the `Set`

data structure, we can greatly enhance the speed of
such lookups. Let’s explore how.

### Problem Setup

Imagine you have two large arrays:

**list1**: A array of 1,000,000 elements.**list2**: A smaller array of 50,000 elements.- Elements in the two arrays are arranged such that the only common element is the last element of both arrays. this is done to find the maximum time taken to find the common element.

Our goal is to find the first common element between these two lists efficiently.

```
const list1 = Array.from({ length: 1000000 }, (_, i) => i + 1);
const list2 = Array.from({ length: 50000 }, (_, i) => i + 1000000).toReversed();
```

In this case, the first common element is `1,000,000`

, but how do we find it
quickly?

### The Naive Approach

Without optimization, one might use a nested loop or methods like `indexOf()`

or
`includes()`

to search through both arrays. However, this results in O(m*n)
complexity, which is far too slow for large datasets.

```
const list1 = Array.from({ length: 1000000 }, (_, i) => i + 1);
const list2 = Array.from({ length: 50000 }, (_, i) => i + 1000000).toReversed();
console.time("lookup");
const common = list1.find((item) => list2.includes(item));
console.timeEnd("lookup");
```

This approach takes about 2230 milliseconds to find the common element.

### The Optimized Approach: Using `Set`

By converting one of the lists into a `Set`

, we can optimize the search process.
A `Set`

provides O(1) average time complexity for lookups, which is much faster
than the O(n) time complexity for arrays. In total this approach has a time
complexity of O(m+n). Here’s how we can leverage it:

- Convert
`list1`

(larger array) into a`Set`

for faster lookups. - Use the
`find()`

method on`list2`

to iterate over the elements and check if they exist in the`Set`

.

Here’s the complete code:

```
const list1 = Array.from({ length: 1000000 }, (_, i) => i + 1);
const list2 = Array.from({ length: 50000 }, (_, i) => i + 1000000).toReversed();
const set = new Set(list1);
console.time("lookup");
const common = list2.find((item) => set.has(item));
console.timeEnd("lookup");
```

This optimized approach takes only about 4 millisecond to find the common element.

### Key Benefits of the Optimized Approach

**Scalability**: As data sizes grow, the performance impact of using a`Set`

becomes more pronounced. The time complexity of the lookup operation is reduced from O(m*n) to O(M+n).**Efficiency**: By leveraging the strengths of`Set`

, the optimized solution provides a much more efficient search process, suitable for handling large datasets.

### Conclusion

When faced with the challenge of finding common elements between two arrays,
using `Set`

in JavaScript is a powerful and efficient solution. It reduces the
computational complexity of the operation, ensuring that your code can handle
large datasets quickly and effectively.

Next time you need to compare large arrays in JavaScript, remember to leverage
the power of `Set`

for faster lookups and efficient code execution!