Mastering Algorithmic Problems with Sets in Python

Introduction

In today's lesson, we'll dive into the world of Python sets . We'll focus on leveraging this powerful data structure to solve two common interview problems. Sets' ability to handle unique elements can simplify and optimize our problem-solving process, making it more efficient. So, if you're ready to discover the power and nuances of using sets to solve problems, let's get started!

Problem 1: Unique String in the List

Our first problem revolves around identifying the first unique string from a list. Imagine you're working on a text analyzing tool that needs to identify the first unique word in a piece of text. This problem simulates such a real-world scenario.

Naive Approach

O(N^2)

Efficient Approach Explanation

Let's introduce Python sets to the stage! The defining property of a set is that it contains unique elements, making it a perfect fit for our current predicament. Our strategy consists of two parts, each tailored to leverage the capabilities of sets: We scan through the words, keeping track of the previously encountered words in a set called seen . A crucial aspect of our solution comes from an inherent feature of sets: if a word is already in seen, adding it again does not change the set. Keeping this in mind, we create a second set, duplicates, consisting only of words that we have previously seen. Once we know which words are duplicates, it becomes elementary to find the first word in our original list that isn't a duplicate. We make another pass over the list, checking each word to see if it's in the duplicates set. The first word we find that isn't a duplicate is our answer. By focusing our solution around sets, we've reduced the problem to two single-pass traversals, giving our solution a linear time complexity of O(2N), a significant improvement over the naive approach.

Join the 1M+ learners on CodeSignal

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

Problem 2: Solution Building

Here's how we fulfill the task:

We first convert every word from both lists to a sorted tuple of its characters to have a unified form for all anagram words.

sorted_tuples_1 = set(tuple(sorted(word)) for word in list_1)
sorted_tuples_2 = set(tuple(sorted(word)) for word in list_2)

Now, those sets themselves have unique character tuples. We find the common tuples between the two, which represent the anagram words.

common_tuples = sorted_tuples_1 & sorted_tuples_2

For the final output, we iterate over the words in the original lists again, and for each word, if its sorted character tuple is present in common_tuples set, we add it to the respective output list.

list_1_output = [word for word in list_1 if tuple(sorted(word)) in common_tuples] # contains anagrams from the first list
list_2_output = [word for word in list_2 if tuple(sorted(word)) in common_tuples] # contains anagrams from the second list

Finally, we return a list of tuples, where each tuple is an anagram pair from list_1_output and list_2_output.

output = []
for word1 in list_1_output:
    for word2 in list_2_output:
        # traversing every pair of words in filtered lists
        if tuple(sorted(word1)) == tuple(sorted(word2)):
            # If words in the pair are anagrams, add them to the output list
            output.append((word1, word2))
return output

The time complexity of this method is $O((n + m) \cdot w \log w + a \cdot b \cdot w \log w)$ , where $n$ and $m$ are sizes of $list_1$ and $list_2$ , respectively, $w$ is the average word length, and $a$ and $b$ are the sizes of list_1_output and list_2_output. In the worst case where most words are anagrams, this becomes $O(n \cdot m \cdot w \log w)$ . While this is still potentially quadratic in terms of list sizes, it's much more efficient than the naive approach in typical cases where only a subset of words have anagrams.

Problem 2: Solution with Dictionaries (Optional)

While this course didn't cover Python dictionaries yet, they are essentially a very powerful tool that can make the solution here even more effective. We are going to dig into Python dictionaries later in this course, but take a moment to go through and try to understand the solution for this problem if dictionaries would be possible to use. This is totally optional; no worries if you don't understand the solution yet; we will learn dictionaries later in this course.

from collections import defaultdict

# Create mapping for `list_1`
mapping_1 = defaultdict(list)
# mapping_1 stores (sorted anagram) -> list[anagrams] mapping for `list_1`
for word in list_1:
    sorted_tuple = tuple(sorted(word)) # unique identifier of the anagram
    mapping_1[sorted_tuple].append(word)
    # `mapping_1[sorted_tuple]` stores all anagrams under the same identifier for `list_1`

# Create mapping for `list_2`
mapping_2 = defaultdict(list)
# mapping_2 stores (sorted anagram) -> list[anagrams] mapping for `list_2`
for word in list_2:
    sorted_tuple = tuple(sorted(word)) # unique identifier of the anagram
    mapping_2[sorted_tuple].append(word)
    # `mapping_2[sorted_tuple]` stores all anagrams under the same identifier for `list_2`

# Intersect keys from mapping_1 and mapping_2 to get common sorted tuples
# Every element in `common_tuples` is an anagram identifier that exists in both lists
common_tuples = set(mapping_1.keys()) & set(mapping_2.keys())

output = []
for anagram_tuple in common_tuples:
    for word1 in mapping_1[anagram_tuple]:
        for word2 in mapping_2[anagram_tuple]:
            # Both word1 and word2 have the same anagram identifier, so are anagrams
            output.append((word1, word2))

return output

This solution will only traverse pairs that are actually anagrams, so the complexity will be $O((n + m) \cdot w \log w + P)$ , where $n$ and $m$ are sizes of $list_1$ and $list_2$ , respectively, $w$ is the average word length, and $P$ is the number of anagram pairs in the output. This is significantly better than the previous approach because we avoid redundant sorting operations and only iterate through actual anagram pairs. Note that if you only need to calculate the number of anagram pairs, the time complexity remains $O((n + m) \cdot w \log w)$ as you can simply count pairs without iterating through them.

list_1_output = [word for word in list_1 if tuple(sorted(word)) in common_tuples] # contains anagrams from the first list list_2_output = [word for word in list_2 if tuple(sorted(word)) in common_tuples] # contains anagrams from the second list

output = [] for word1 in list_1_output: for word2 in list_2_output: # traversing every pair of words in filtered lists if tuple(sorted(word1)) == tuple(sorted(word2)): # If words in the pair are anagrams, add them to the output list output.append((word1, word2)) return output

from collections import defaultdict # Create mapping for `list_1` mapping_1 = defaultdict(list) # mapping_1 stores (sorted anagram) -> list[anagrams] mapping for `list_1` for word in list_1: sorted_tuple = tuple(sorted(word)) # unique identifier of the anagram mapping_1[sorted_tuple].append(word) # `mapping_1[sorted_tuple]` stores all anagrams under the same identifier for `list_1` # Create mapping for `list_2` mapping_2 = defaultdict(list) # mapping_2 stores (sorted anagram) -> list[anagrams] mapping for `list_2` for word in list_2: sorted_tuple = tuple(sorted(word)) # unique identifier of the anagram mapping_2[sorted_tuple].append(word) # `mapping_2[sorted_tuple]` stores all anagrams under the same identifier for `list_2` # Intersect keys from mapping_1 and mapping_2 to get common sorted tuples # Every element in `common_tuples` is an anagram identifier that exists in both lists common_tuples = set(mapping_1.keys()) & set(mapping_2.keys()) output = [] for anagram_tuple in common_tuples: for word1 in mapping_1[anagram_tuple]: for word2 in mapping_2[anagram_tuple]: # Both word1 and word2 have the same anagram identifier, so are anagrams output.append((word1, word2)) return output

Introduction

Problem 1: Unique String in the List

Naive Approach

Efficient Approach Explanation

Join the 1M+ learners on CodeSignal

Solution Building

Problem 2: Anagram Pairs in Two Lists

Problem 2: Problem Actualization

Problem 2: Naive Approach

Problem 2: Efficient Approach Explanation

Problem 2: Solution Building

Problem 2: Solution with Dictionaries (Optional)

Lesson Summary

Practice Exercises