Exploring Sets in TypeScript: Ensuring Uniqueness and Optimizing Performance
Introduction to the Lesson
Today, we will tackle two problems demonstrating how TypeScript sets can streamline your code and optimize performance. TypeScript offers additional benefits, such as type safety, when handling collections of unique items. This makes sets the ideal data structure for solving uniqueness and membership testing problems while ensuring all items adhere to specified types.
Problem 1: Check if Two Sets are Disjoint
Let's begin by considering the function areDisjoint, which takes two arrays and determines if they are disjoint, meaning they have no elements in common. This is crucial when analyzing datasets for overlapping values, similar to ensuring that two puzzle pieces from different puzzles don't fit together.
Imagine two companies looking to cross-promote products but wishing to target customers who have yet to interact with both brands. Ensuring that their promotional efforts are disjoint becomes essential.
Problem 1: Naive Approach
A naive approach would be to iterate over every element in the first array and, for each one, check every element in the second array for a match. This can be inefficient for larger datasets, making this method prohibitive due to its time complexity of O(n⋅m).
Problem 1: Efficient Solution Building
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal
Consider a scenario with a list of names and a super-fast scanner that can immediately tell you whether a name is on the list. In TypeScript terms, this is what sets offer via their has method — a way to check presence in constant time, O(1).
We can also check if an element has some matches for a given condition with the some method, which has a time complexity of O(n).
Let's build the solution, with this analogy in mind, step by step:
Transfer the elements of one array into our super-fast scanner, a.k.a. a set called set1.
Feed names from the other array to the scanner using the .some() method to check if set1 can find a match.
Since we want to determine whether there are no twins (common elements), we invert the result of .some() because it returns true if it finds at least one match.
TypeScript
// Defining the function areDisjointfunction areDisjoint<T>(array1: T[], array2: T[]): boolean { const set1 = new Set(array1); return !array2.some(element => set1.has(element));}// Example calls to the function, highlighting the differences in arraysconsole.log(areDisjoint(['Alice', 'Bob', 'Charlie'], ['Xander', 'Yasmine', 'Zane'])); // true, no common namesconsole.log(areDisjoint(['Alice', 'Bob', 'Charlie'], ['Charlie', 'Delta', 'Echo'])); // false, 'Charlie' is common to both
This code illustrates how sets can quickly indicate whether two lists share elements, producing true for completely disjoint lists and false otherwise.
Problem 1: Time complexity
Problem 2: Remove Duplicates in an Array
Now, we move on to a common data-cleaning problem: removing duplicates from an array. Just like a librarian cataloging books, duplicates waste space and cause confusion. We want our array to contain unique entries.
Problem 2: Approaches
Problem 2: Solution Building
Let's apply this in code:
First, we create a set from our array, serving as an assistant that automatically filters out duplicate names from our lists.
Then, we convert our set, now containing unique names, back into an array, ready for use.
These examples demonstrate how sets elegantly handle duplicate removal, producing arrays that succinctly represent the unique elements they originally contained.
Problem 2: Time complexity
Lesson Summary
In today's lesson, we've reinforced the power of TypeScript sets for solving common algorithmic problems efficiently while leveraging type safety. We explored how sets can be used in scenarios like ensuring disjointness and eliminating duplicates, underscoring their versatility in TypeScript. Let's continue to the practice exercises to witness these concepts in action!
The creation of set1 from array1 has a time complexity of O(m), where m is the length of array1. Searching for a match with the some method in array2 has a complexity of O(n), where n is the length of array2. So, the overall time complexity is O(m+n).
The naive approach would involve creating a new list and adding only those items that aren't present. This method is impractical for a library of any considerable size due to its time complexity of O(n2).
Let's consider the efficient approach. Enter TypeScript sets, which adhere to the principle that each member is unique. By converting our array into a set, we automatically remove duplicates.
Creating a set with new Set(array) takes O(n) time, while creating an array from the set via the Array.from() method also takes O(n) time. Since we remove constants from our overall time complexity, ultimately the removal of duplicates takes O(n) time.
