Mastering Unique Elements and Anagram Detection with Go Maps

Introduction

Welcome to our focused exploration of Go's maps and their valuable applications in solving algorithmic challenges. Building upon the foundation laid in the first unit, this lesson will delve into how these efficient data structures can be leveraged to address and solve various 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 repeated identifiers and finding one identifier towards the end of the list that is unlike any other.

Naive Approach

O(n^2)

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

Efficient Approach

We'll create a unique signature for each word by sorting its characters and then compare these signatures for matches. We'll use a map to store signatures for efficient access.

Here's the implementation for efficiently finding anagrams:

import "sort"

// Function to sort characters of a word
func SortCharacters(word string) string {
    chars := []rune(word)
    sort.Slice(chars, func(i, j int) bool {
        return chars[i] < chars[j]
    })
    return string(chars)
}

func FindAnagramsEfficient(array1, array2 []string) []string {
    // Create a map to store sorted signatures of words in array2
    sortedWordsInArray2 := make(map[string]bool)
    for _, word := range array2 {
        sortedWordsInArray2[SortCharacters(word)] = true
    }

    result := []string{}
    // Track matched anagrams to avoid duplicates
    anagramsMatched := make(map[string]bool)
    for _, word := range array1 {
        sortedWord := SortCharacters(word)
        // Check for anagram match and ensure no duplicate in result
        if sortedWordsInArray2[sortedWord] && !anagramsMatched[word] {
            result = append(result, word)
            anagramsMatched[word] = true
        }
    }

    return result
}

Explanation:

We define a helper function SortCharacters that returns the sorted character representation of a word, which acts as a signature for an anagram.
We create a map sortedWordsInArray2 where each key represents the sorted signature of words from array2. This helps quickly identify if a word from array1 has an anagram in array2.
As we iterate over array1, we find the sorted signature for each word and check if it exists in sortedWordsInArray2. We use another map anagramsMatched to avoid adding duplicate words to the result list.

By utilizing Go's maps in this manner, we achieve efficient anagram checking with reduced complexity. The time complexity is $O(m \cdot k \log k + n \cdot k \log k)$ , where m is the number of words in array2, n is the number of words in array1, and k is the average length of the words.

Notice how the time complexity now doesn't multiply n and m, but rather adds them. This shows that we have significantly reduced the time needed to get to a solution compared to the naive approach.

import "sort" func SortCharacters(word string) string { chars := []rune(word) sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] }) return string(chars) } func FindAnagramsNaive(array1, array2 []string) []string { result := []string{} // Compare every word in array1 with every word in array2 for _, word1 := range array1 { for _, word2 := range array2 { // If sorted characters match, they are anagrams if SortCharacters(word1) == SortCharacters(word2) { // Avoid duplicates in the result if !contains(result, word1) { result = append(result, word1) } break } } } return result } func contains(s []string, e string) bool { // Check for the presence of a word in the result slice for _, a := range s { if a == e { return true } } return false }

import "sort" // Function to sort characters of a word func SortCharacters(word string) string { chars := []rune(word) sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] }) return string(chars) } func FindAnagramsEfficient(array1, array2 []string) []string { // Create a map to store sorted signatures of words in array2 sortedWordsInArray2 := make(map[string]bool) for _, word := range array2 { sortedWordsInArray2[SortCharacters(word)] = true } result := []string{} // Track matched anagrams to avoid duplicates anagramsMatched := make(map[string]bool) for _, word := range array1 { sortedWord := SortCharacters(word) // Check for anagram match and ensure no duplicate in result if sortedWordsInArray2[sortedWord] && !anagramsMatched[word] { result = append(result, word) anagramsMatched[word] = true } } return result }

Introduction

Problem 1: Unique Echo

Naive Approach

Efficient Approach

Join the 1M+ learners on CodeSignal

Problem 2: Anagram Matcher

Naive Approach

Efficient Approach

Lesson Summary