Mastering Algorithmic Problems with Sets in Python

Mastering Algorithmic Problems with Sets in Python | CodeSignal Learn

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

Solution Building

Let's break down our solution: 1. In the initial iteration over words, if a word already exists in the seen set, we identify it as a duplicate and add it to duplicates . If not, the word is added to seen . Python def find_unique_string(words): seen = set() duplicates = set() for word in words: if word in seen: duplicates.add(word) seen.add(word) def find_unique_string(words): seen = set() duplicates = set() for word in words: if word in seen: duplicates.add(word) seen.add(word) This code creates two sets. seen contains all words we've come across, and duplicates contains words that have appeared more than once. To visualize it, consider words as 'apple', 'banana', 'apple'. After the above block of code, we'd have seen as 'apple', 'banana', and duplicates as 'apple'. 2. In the next phase of our solution, we iterate over words again, checking if a word is in duplicates . The first word that is not in duplicates is our answer as it's the first unique string in the list. If we don't find any unique string, we return an empty string. Python for word in words: if word not in duplicates: return word return "" for word in words: if word not in duplicates: return word return "" Thanks to two simple traversals, we've efficiently solved a problem that initially seemed complex.

Problem 2: Solution Building

O((n + m) \cdot w \log w + a \cdot b \cdot w \log w)

Problem 2: Solution with Dictionaries (Optional)

O((n + m) \cdot w \log w + P)

The most straightforward approach to this problem would involve checking each word from the first list against each word from the second list to find anagrams. While this would provide correct results, it's an inefficient method with a time complexity of $O(n \cdot m \cdot w)$ , where $n$ is the size of the first list of words, $m$ is the size of the second list of words, and $w$ is the average word length. As you can see, it gets impractically slow for larger inputs.

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.

Python

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

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.

Python

common_tuples = sorted_tuples_1 & sorted_tuples_2

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.

Python

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

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.

Python

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

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.

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.

Python

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

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.