🔑 PHP Hashing Patterns

Pattern 1 — Frequency Map

Count occurrences; use for anagram detection, top-K elements, majority vote.

// Anagram check
function isAnagram(string $s, string $t): bool {
    if (strlen($s) !== strlen($t)) return false;
    $freq = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $freq[$s[$i]] = ($freq[$s[$i]] ?? 0) + 1;
        $freq[$t[$i]] = ($freq[$t[$i]] ?? 0) - 1;
    }
    foreach ($freq as $v) if ($v !== 0) return false;
    return true;
}

---

Pattern 2 — Two-Pointer Complement Lookup

Store complements as you iterate; O(n) time instead of O(n²).

function twoSum(array $nums, int $target): array {
    $map = [];
    foreach ($nums as $i => $n) {
        if (isset($map[$target - $n])) return [$map[$target - $n], $i];
        $map[$n] = $i;
    }
    return [];
}

---

Pattern 3 — Prefix Sum + Hash Map

Subarray sum problems: store running sum → count of occurrences.

function subarraySum(array $nums, int $k): int {
    $map = [0 => 1]; $sum = 0; $count = 0;
    foreach ($nums as $n) {
        $sum += $n;
        $count += $map[$sum - $k] ?? 0;
        $map[$sum] = ($map[$sum] ?? 0) + 1;
    }
    return $count;
}

---

Pattern 4 — Sliding Window + Frequency

Fixed or variable window with character/element frequency tracking.

// Find all anagrams in a string (fixed window)
function findAnagrams(string $s, string $p): array {
    if (strlen($s) < strlen($p)) return [];
    $need = []; $have = []; $result = [];
    for ($i = 0; $i < strlen($p); $i++) {
        $need[$p[$i]] = ($need[$p[$i]] ?? 0) + 1;
        $have[$s[$i]] = ($have[$s[$i]] ?? 0) + 1;
    }
    $pLen = strlen($p); $matched = 0;
    foreach ($need as $c => $cnt) if (($have[$c] ?? 0) === $cnt) $matched++;
    if ($matched === count($need)) $result[] = 0;
    for ($i = $pLen; $i < strlen($s); $i++) {
        // Add right
        $r = $s[$i]; $have[$r] = ($have[$r] ?? 0) + 1;
        if (isset($need[$r]) && $have[$r] === $need[$r]) $matched++;
        if (isset($need[$r]) && $have[$r] === $need[$r] + 1) $matched--;
        // Remove left
        $l = $s[$i - $pLen]; $have[$l]--;
        if (isset($need[$l]) && $have[$l] === $need[$l]) $matched++;
        if (isset($need[$l]) && $have[$l] === $need[$l] - 1) $matched--;
        if ($matched === count($need)) $result[] = $i - $pLen + 1;
    }
    return $result;
}

---

Pattern 5 — Group By Key

Use a computed key to group elements (e.g., sorted chars for anagrams).

function groupAnagrams(array $strs): array {
    $groups = [];
    foreach ($strs as $s) {
        $key = str_split($s);
        sort($key);
        $groups[implode('', $key)][] = $s;
    }
    return array_values($groups);
}

---

Pattern 6 — Index as Hash (In-Place)

Mark visited indices by negating values — O(1) extra space.

function firstMissingPositive(array $nums): int {
    $n = count($nums);
    // Step 1: Move 1..n into correct positions
    for ($i = 0; $i < $n; $i++) {
        while ($nums[$i] >= 1 && $nums[$i] <= $n && $nums[$nums[$i]-1] !== $nums[$i])
            [$nums[$i], $nums[$nums[$i]-1]] = [$nums[$nums[$i]-1], $nums[$i]];
    }
    // Step 2: Find first mismatch
    for ($i = 0; $i < $n; $i++) if ($nums[$i] !== $i + 1) return $i + 1;
    return $n + 1;
}

---

Pattern 7 — Dual Map (Bijection)

Two maps verifying one-to-one correspondence.

function isIsomorphic(string $s, string $t): bool {
    $st = []; $ts = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $cs = $s[$i]; $ct = $t[$i];
        if (isset($st[$cs]) && $st[$cs] !== $ct) return false;
        if (isset($ts[$ct]) && $ts[$ct] !== $cs) return false;
        $st[$cs] = $ct; $ts[$ct] = $cs;
    }
    return true;
}

---

Complexity Summary