Deciphering Uniqueness and Anagram Mysteries with PHP Arrays

Deciphering Uniqueness and Anagram Mysteries with PHP Arrays | CodeSignal Learn

Lesson Introduction

Welcome to our focused exploration of PHP's array functions and their powerful applications in algorithmic challenges. In this lesson, " Deciphering Uniqueness and Anagram Mysteries with PHP Arrays," we'll delve into how these functions can be harnessed to efficiently tackle problems commonly seen in technical interviews.

Problem 1: Unique Echo

Imagine: you’re presented with an extensive list of words, with the task to pinpoint the final word that stands alone — the last non-repeating word. This mirrors the challenge of sorting through a database of unique identifiers to identify a distinct one near the end.

Problem 1: Naive Approach

O(n^2)

Problem 1: Efficient Approach

O(n)

Problem 2: Anagram Matcher

Next, consider a scenario with two arrays of strings, aiming to identify all words in the first array with an anagram present in the second array.

Problem 2: Efficient Approach

O(m \log m)

Lesson Summary

Throughout this lesson, we harnessed PHP's array functions to solve the "Unique Echo" and "Anagram Matcher" challenges efficiently. These techniques underscore the importance of using PHP's array operations to manage complexity, a skill revered in technical interviews. Next, you’ll engage in hands-on exercises to deepen your understanding and refinement of these computational techniques.

Previous Lesson

Next Lesson: Managing Key-Value Pairs with PHP Associative Arrays

Join the 1M+ learners on CodeSignal

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

A straightforward solution iterates in reverse through each word, comparing it with every other word to check for uniqueness. This brute-force approach results in a time complexity of $O(n^2)$ , making it impractical for large datasets, where $n$ is the number of words.

We can capitalize on associative arrays in PHP to efficiently count word occurrences and identify uniqueness:

Initialize an associative array for word counts:
PHP
```
$wordCounts = [];
```

Count each word's occurrences as you traverse the list:

PHP

foreach ($words as $word) {
    if (isset($wordCounts[$word])) {
        $wordCounts[$word]++;
    } else {
        $wordCounts[$word] = 1;
    }
}

Identify the last unique word by traversing the array from the end:

PHP

$lastUniqueWord = "";
for ($i = count($words) - 1; $i >= 0; $i--) {
    if ($wordCounts[$words[$i]] == 1) {
        $lastUniqueWord = $words[$i];
        break;
    }
}

$lastUniqueWord = "";
for ($i = count($words) - 1; $i >= 0; $i--) {
    if ($wordCounts[$words[$i]] == 1) {
        $lastUniqueWord = $words[$i];
        break;
    }
}

Return the unique word:

PHP

return $lastUniqueWord;

return $lastUniqueWord;

Here is the full code!

PHP

<?php
function findLastUniqueWord($words) {
    // Step 1: Initialize an associative array for word counts
    $wordCounts = [];

    // Step 2: Count each word's occurrences as you traverse the list
    foreach ($words as $word) {
        if (isset($wordCounts[$word])) {
            $wordCounts[$word]++;
        } else {
            $wordCounts[$word] = 1;
        }
    }

    // Step 3: Identify the last unique word by traversing the array from the end
    $lastUniqueWord = "";
    for ($i = count($words) - 1; $i >= 0; $i--) {
        if ($wordCounts[$words[$i]] == 1) {
            $lastUniqueWord = $words[$i];
            break;
        }
    }

    // Step 4: Return the unique word
    return $lastUniqueWord;
}

// Example usage
$words = ["apple", "banana", "apple", "orange", "banana", "kiwi"];
echo findLastUniqueWord($words); // Output: kiwi
?>

<?php
function findLastUniqueWord($words) {
    // Step 1: Initialize an associative array for word counts
    $wordCounts = [];

    // Step 2: Count each word's occurrences as you traverse the list
    foreach ($words as $word) {
        if (isset($wordCounts[$word])) {
            $wordCounts[$word]++;
        } else {
            $wordCounts[$word] = 1;
        }
    }

    // Step 3: Identify the last unique word by traversing the array from the end
    $lastUniqueWord = "";
    for ($i = count($words) - 1; $i >= 0; $i--) {
        if ($wordCounts[$words[$i]] == 1) {
            $lastUniqueWord = $words[$i];
            break;
        }
    }

    // Step 4: Return the unique word
    return $lastUniqueWord;
}

// Example usage
$words = ["apple", "banana", "apple", "orange", "banana", "kiwi"];
echo findLastUniqueWord($words); // Output: kiwi
?>

This approach accomplishes a time complexity of $O(n)$ . Iterating through the list twice (once for counting and once for finding uniqueness) is linear, as each operation on an associative array (insert or lookup) generally has an average time complexity of $O(1)$ .

To efficiently find anagrams, we'll assign a sorted character signature to each word, leveraging PHP arrays for efficient lookups:

Create a function to produce sorted character signatures:

PHP

function sortCharacters($input) {
    $characters = str_split($input);
    sort($characters);
    return implode('', $characters);
}

function sortCharacters($input) {
    $characters = str_split($input);
    sort($characters);
    return implode('', $characters);
}

Store signatures from array2 in an associative array for quick comparison:

PHP

$sortedWordsInArray2 = [];
foreach ($array2 as $word) {
    $sortedWordsInArray2[sortCharacters($word)] = true;
}

$sortedWordsInArray2 = [];
foreach ($array2 as $word) {
    $sortedWordsInArray2[sortCharacters($word)] = true;
}

Find anagrams by comparing each word's signature in array1 with stored signatures:

PHP

$result = [];
foreach ($array1 as $word) {
    $sortedWord = sortCharacters($word);
    if (isset($sortedWordsInArray2[$sortedWord])) {
        $result[] = $word;
    }
}

$result = [];
foreach ($array1 as $word) {
    $sortedWord = sortCharacters($word);
    if (isset($sortedWordsInArray2[$sortedWord])) {
        $result[] = $word;
    }
}

Return the list of anagrams:
PHP
```
return $result;
```
```
return $result;
```

Here is the full code!

PHP

<?php
function sortCharacters($input) {
    $characters = str_split($input);
    sort($characters);
    return implode('', $characters);
}

function findAnagrams($array1, $array2) {
    // Step 2: Store signatures from array2 in an associative array for quick comparison
    $sortedWordsInArray2 = [];
    foreach ($array2 as $word) {
        $sortedWordsInArray2[sortCharacters($word)] = true;
    }

    // Step 3: Find anagrams by comparing each word's signature in array1 with stored signatures
    $result = [];
    foreach ($array1 as $word) {
        $sortedWord = sortCharacters($word);
        if (isset($sortedWordsInArray2[$sortedWord])) {
            $result[] = $word;
        }
    }

    // Step 4: Return the list of anagrams
    return $result;
}

// Example usage
$array1 = ["listen", "silent", "enlist", "google"];
$array2 = ["inlets", "banana", "google"];

print_r(findAnagrams($array1, $array2)); // Output: Array ( [0] => listen [1] => silent [2] => enlist [3] => google )
?>

<?php
function sortCharacters($input) {
    $characters = str_split($input);
    sort($characters);
    return implode('', $characters);
}

function findAnagrams($array1, $array2) {
    // Step 2: Store signatures from array2 in an associative array for quick comparison
    $sortedWordsInArray2 = [];
    foreach ($array2 as $word) {
        $sortedWordsInArray2[sortCharacters($word)] = true;
    }

    // Step 3: Find anagrams by comparing each word's signature in array1 with stored signatures
    $result = [];
    foreach ($array1 as $word) {
        $sortedWord = sortCharacters($word);
        if (isset($sortedWordsInArray2[$sortedWord])) {
            $result[] = $word;
        }
    }

    // Step 4: Return the list of anagrams
    return $result;
}

// Example usage
$array1 = ["listen", "silent", "enlist", "google"];
$array2 = ["inlets", "banana", "google"];

print_r(findAnagrams($array1, $array2)); // Output: Array ( [0] => listen [1] => silent [2] => enlist [3] => google )
?>

This method achieves significant efficiency through the combination of character sorting and associative array lookups. The total complexity is dominated by the sorting operation, which operates in $O(m \log m)$ for each word (where $m$ is the average length of the words). Hence, the overall complexity is $O(n \cdot m \log m + k \cdot m \log m)$ , with $n$ and $k$ being the numbers of words in array1 and array2, respectively.