Unraveling Uniqueness and Anagram Mysteries with JavaScript Sets

Unraveling Uniqueness and Anagram Mysteries with JavaScript Sets | CodeSignal Learn

Lesson Introduction

Welcome to our focused exploration of JavaScript's Set and its remarkable applications in solving algorithmic challenges. In this lesson, " Unraveling Uniqueness and Anagram Mysteries with JavaScript Sets ", we'll explore how this powerful data structure can be used to approach and solve certain types of problems commonly encountered in technical interviews.

Problem 1: Unique Echo

Picture this: you're given a vast list of words, and you must identify the final word that stands proudly solitary — the last word that is not repeated. Imagine sorting through a database of unique identifiers and finding one identifier towards the end of the list that is unlike any others.

Problem 1: Naive Approach

O(n^2)

Problem 1: Efficient Approach

O(n)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

The straightforward approach would be to examine each word in reverse, comparing it to every other word for uniqueness. This brute-force method would result in poor time complexity, $O(n^2)$ , which is less than ideal for large datasets.

We can use two Set instances: wordsSet to maintain unique words and duplicatesSet to keep track of duplicate words. By the end, we can remove all duplicated words from wordsSet to achieve our goal. Here is how to use Set to solve the problem:

Create a Set instance to store unique words:

JavaScript

let wordsSet = new Set();

Initialize another Set to monitor duplicates:

JavaScript

let duplicatesSet = new Set();

Iterate the word array, filling wordsSet and duplicatesSet:

JavaScript

for (let word of words) {
    if (wordsSet.has(word)) {
        duplicatesSet.add(word);
    } else {
        wordsSet.add(word);
    }
}

for (let word of words) {
    if (wordsSet.has(word)) {
        duplicatesSet.add(word);
    } else {
        wordsSet.add(word);
    }
}

Use a loop to remove all duplicated words from wordsSet:

JavaScript

duplicatesSet.forEach(word => wordsSet.delete(word));

duplicatesSet.forEach(word => wordsSet.delete(word));

Now, wordsSet only contains unique words. Find the last unique word by iterating through the original word list from the end:

JavaScript

let lastUniqueWord = "";
for(let i = words.length - 1; i >= 0; i--){
    if(wordsSet.has(words[i])){
        lastUniqueWord = words[i];
        break;
    }
}

let lastUniqueWord = "";
for(let i = words.length - 1; i >= 0; i--){
    if(wordsSet.has(words[i])){
        lastUniqueWord = words[i];
        break;
    }
}

And finally, return the last unique word:

JavaScript

return lastUniqueWord;

return lastUniqueWord;

This efficient approach, with a time complexity closer to $O(n)$ , is far superior to the naive method and showcases your proficiency at solving algorithmic problems with JavaScript's Set.

Problem 2: Solution Building

O(m\log m)

Let's break down the anagram matcher:

Construct a function to create sorted character signatures from the input string:

JavaScript

function sortCharacters(input) {
    return [...input].sort().join('');
}

Store these sorted characters from array2 in a Set for fast lookup:

JavaScript

let sortedWordsInArray2 = new Set();
array2.forEach(word => sortedWordsInArray2.add(sortCharacters(word)));

For each word in array1, check for its sorted signature in the Set and track the found anagrams:

JavaScript

let result = [];
for (let word of array1) {
    let sortedWord = sortCharacters(word);
    if (sortedWordsInArray2.has(sortedWord)) {
        result.push(word);
    }
}

The Array result stores the matches, ensuring that we return anagrams.

Our final step is to return the list of anagrams found:

JavaScript

return result;

return result;

By utilizing Sets in this manner, we achieve efficient anagram checking with reduced complexity, considering both the $O(m\log m)$ character sorting for each word and the $O(n)$ comparison for $n$ words.