🎯 PHP Hashing — Top 25 Interview Questions

---

Q1 — Two Sum

🧠 How to Approach This

Step 1 — Recognize the pattern: Complement lookup — store seen values in a map.

Step 2 — Brute force (what NOT to do): Nested loops O(n²) — check every pair.

Step 3 — Optimal insight: As you iterate, check if complement (target - n) is already in map.

Step 4 — Algorithm:

1. For each num: if target-num in map → return [map[complement], i]

2. Else map[num] = i

Step 5 — Edge cases: Same index used twice (impossible since we check before inserting).

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

Time: O(n) | Space: O(n)

---

Q2 — Group Anagrams

🧠 How to Approach This

Step 1 — Recognize the pattern: Anagrams share the same sorted character key.

Step 2 — Brute force (what NOT to do): Compare each pair — O(n² · k log k).

Step 3 — Optimal insight: Sort each string as a key; group by key in a map.

Step 4 — Algorithm:

1. For each string: sort chars → key

2. Group strings by key

Step 5 — Edge cases: Single string; empty string.

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

Time: O(n · k log k) | Space: O(n · k)

---

Q3 — Top K Frequent Elements

🧠 How to Approach This

Step 1 — Recognize the pattern: Frequency map + bucket sort by frequency.

Step 2 — Brute force (what NOT to do): Sort all by frequency — O(n log n).

Step 3 — Optimal insight: Bucket sort: index = frequency (max n), return top-k from highest bucket.

Step 4 — Algorithm:

1. Build frequency map

2. Bucket by frequency (index 0..n)

3. Scan buckets from high to low; collect k elements

Step 5 — Edge cases: All elements unique; k = n.

function topKFrequent(array $nums, int $k): array {
    $freq = [];
    foreach ($nums as $n) $freq[$n] = ($freq[$n] ?? 0) + 1;
    $buckets = array_fill(0, count($nums) + 1, []);
    foreach ($freq as $n => $f) $buckets[$f][] = $n;
    $result = [];
    for ($i = count($buckets) - 1; $i >= 0 && count($result) < $k; $i--)
        foreach ($buckets[$i] as $n) { $result[] = $n; if (count($result) === $k) break; }
    return $result;
}

Time: O(n) | Space: O(n)

---

Q4 — Valid Anagram

🧠 How to Approach This

Step 1 — Recognize the pattern: Frequency balance — increment for s, decrement for t.

Step 2 — Brute force (what NOT to do): Sort both strings — O(n log n).

Step 3 — Optimal insight: Single frequency array; all must reach zero.

Step 4 — Algorithm:

1. If lengths differ → false

2. freq[c]++ for s, freq[c]-- for t

3. Any non-zero → false

Step 5 — Edge cases: Unicode characters; empty strings.

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;
}

Time: O(n) | Space: O(1) — at most 26 chars

---

Q5 — Contains Duplicate

🧠 How to Approach This

Step 1 — Recognize the pattern: HashSet membership check as you iterate.

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: If element already in set → duplicate found.

Step 4 — Algorithm:

1. For each num: if in seen → return true; add to seen

2. Return false

Step 5 — Edge cases: Empty array → false; single element → false.

function containsDuplicate(array $nums): bool {
    $seen = [];
    foreach ($nums as $n) {
        if (isset($seen[$n])) return true;
        $seen[$n] = true;
    }
    return false;
}

Time: O(n) | Space: O(n)

---

Q6 — LRU Cache

🧠 How to Approach This

Step 1 — Recognize the pattern: HashMap + Doubly Linked List (O(1) get + O(1) evict).

Step 2 — Brute force (what NOT to do): Array with linear search — O(n) per operation.

Step 3 — Optimal insight: Map for O(1) lookup; DLL for O(1) move-to-front and evict.

Step 4 — Algorithm:

1. get(key): if exists → move to front, return val; else -1

2. put(key, val): if exists → update + move front; else insert front; if over capacity → remove tail

Step 5 — Edge cases: Capacity 1; repeated puts of same key.

class LRUCache {
    private int $cap;
    private array $map = []; // key → node
    private array $head; // dummy head
    private array $tail; // dummy tail

    public function __construct(int $capacity) {
        $this->cap  = $capacity;
        $this->head = ['key'=>null,'val'=>null,'prev'=>null,'next'=>null];
        $this->tail = ['key'=>null,'val'=>null,'prev'=>null,'next'=>null];
        $this->head['next'] = &$this->tail;
        $this->tail['prev'] = &$this->head;
    }
    public function get(int $key): int {
        if (!isset($this->map[$key])) return -1;
        $this->moveToFront($this->map[$key]);
        return $this->map[$key]['val'];
    }
    public function put(int $key, int $value): void {
        if (isset($this->map[$key])) { $this->map[$key]['val']=$value; $this->moveToFront($this->map[$key]); return; }
        $node=['key'=>$key,'val'=>$value,'prev'=>null,'next'=>null];
        $this->map[$key]=&$node; $this->addFront($node);
        if (count($this->map)>$this->cap) { $lru=$this->tail['prev']; $this->remove($lru); unset($this->map[$lru['key']]); }
    }
    private function addFront(array &$node): void { $node['next']=&$this->head['next']; $node['prev']=&$this->head; $this->head['next']['prev']=&$node; $this->head['next']=&$node; }
    private function remove(array &$node): void { $node['prev']['next']=&$node['next']; $node['next']['prev']=&$node['prev']; }
    private function moveToFront(array &$node): void { $this->remove($node); $this->addFront($node); }
}

Time: O(1) get/put | Space: O(capacity)

---

Q7 — Subarray Sum Equals K

🧠 How to Approach This

Step 1 — Recognize the pattern: Prefix sum; count(sum - k) tells us how many subarrays end here sum to k.

Step 2 — Brute force (what NOT to do): All subarrays O(n²) or O(n³).

Step 3 — Optimal insight: Map stores prefix sum → count; look up sum-k each step.

Step 4 — Algorithm:

1. map[0]=1; sum=0, result=0

2. sum += n; result += map[sum-k] ?? 0; map[sum]++

Step 5 — Edge cases: Negative numbers; k=0.

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;
}

Time: O(n) | Space: O(n)

---

Q8 — Longest Consecutive Sequence

🧠 How to Approach This

Step 1 — Recognize the pattern: For each sequence start, count streak length using HashSet.

Step 2 — Brute force (what NOT to do): Sort then count — O(n log n).

Step 3 — Optimal insight: Only start counting from sequence start (no n-1 in set).

Step 4 — Algorithm:

1. Build set from nums

2. For each n: if n-1 not in set → count streak n, n+1, n+2...

3. Track max streak

Step 5 — Edge cases: Empty array; duplicates.

function longestConsecutive(array $nums): int {
    $set = array_flip($nums); $best = 0;
    foreach ($nums as $n) {
        if (!isset($set[$n - 1])) {
            $curr = $n; $streak = 1;
            while (isset($set[$curr + 1])) { $curr++; $streak++; }
            $best = max($best, $streak);
        }
    }
    return $best;
}

Time: O(n) | Space: O(n)

---

Q9 — 4Sum II

🧠 How to Approach This

Step 1 — Recognize the pattern: Split 4 arrays into 2 pairs; count matching complement sums.

Step 2 — Brute force (what NOT to do): 4 nested loops — O(n⁴).

Step 3 — Optimal insight: Map all sums of first two arrays; scan sums of last two for -(sum).

Step 4 — Algorithm:

1. Build map: a+b → count for all pairs in A,B

2. For all c,d: result += map[-(c+d)] ?? 0

Step 5 — Edge cases: All zeros; empty arrays.

function fourSumCount(array $nums1, array $nums2, array $nums3, array $nums4): int {
    $map = []; $count = 0;
    foreach ($nums1 as $a) foreach ($nums2 as $b) $map[$a+$b] = ($map[$a+$b] ?? 0) + 1;
    foreach ($nums3 as $c) foreach ($nums4 as $d) $count += $map[-($c+$d)] ?? 0;
    return $count;
}

Time: O(n²) | Space: O(n²)

---

Q10 — Intersection of Two Arrays

🧠 How to Approach This

Step 1 — Recognize the pattern: HashSet for first array; check second array elements.

Step 2 — Brute force (what NOT to do): Nested loops — O(n·m).

Step 3 — Optimal insight: Set from nums1; iterate nums2, collect matches once.

Step 4 — Algorithm:

1. set1 = set(nums1)

2. For each in nums2: if in set1 → add to result set

Step 5 — Edge cases: No intersection; duplicate elements.

function intersection(array $nums1, array $nums2): array {
    $set = array_flip($nums1); $result = [];
    foreach ($nums2 as $n) {
        if (isset($set[$n])) { $result[$n] = true; }
    }
    return array_keys($result);
}

Time: O(n + m) | Space: O(n)

---

Q11 — Happy Number

🧠 How to Approach This

Step 1 — Recognize the pattern: Cycle detection using HashSet or Floyd's algorithm.

Step 2 — Brute force (what NOT to do): Run indefinitely without cycle detection.

Step 3 — Optimal insight: Track seen numbers; if 1 → happy; if repeat → not happy.

Step 4 — Algorithm:

1. While n != 1 and n not in seen: compute sum of digit squares; add to seen

2. Return n === 1

Step 5 — Edge cases: n=1 immediately happy; n=7 is happy.

function isHappy(int $n): bool {
    $seen = [];
    while ($n !== 1) {
        if (isset($seen[$n])) return false;
        $seen[$n] = true;
        $sum = 0;
        while ($n > 0) { $d = $n % 10; $sum += $d * $d; $n = intdiv($n, 10); }
        $n = $sum;
    }
    return true;
}

Time: O(log n) | Space: O(log n)

---

Q12 — Isomorphic Strings

🧠 How to Approach This

Step 1 — Recognize the pattern: Bijection check — dual maps ensuring one-to-one mapping.

Step 2 — Brute force (what NOT to do): Compare all possible mappings.

Step 3 — Optimal insight: Two maps (s→t and t→s); conflict in either = not isomorphic.

Step 4 — Algorithm:

1. For each pair (cs, ct): check s→t map and t→s map for conflicts

Step 5 — Edge cases: Single char strings; repeated same chars.

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;
}

Time: O(n) | Space: O(1)

---

Q13 — Word Pattern

🧠 How to Approach This

Step 1 — Recognize the pattern: Bijection — same as isomorphic strings but word-level.

Step 2 — Brute force (what NOT to do): Generate all pattern mappings.

Step 3 — Optimal insight: Two maps: char→word and word→char; conflict = false.

Step 4 — Algorithm:

1. Split s into words; if count differs from pattern length → false

2. Dual map check per position

Step 5 — Edge cases: Pattern length ≠ word count.

function wordPattern(string $pattern, string $s): bool {
    $words = explode(' ', $s);
    if (strlen($pattern) !== count($words)) return false;
    $cw = []; $wc = [];
    for ($i = 0; $i < strlen($pattern); $i++) {
        $c = $pattern[$i]; $w = $words[$i];
        if (isset($cw[$c]) && $cw[$c] !== $w) return false;
        if (isset($wc[$w]) && $wc[$w] !== $c) return false;
        $cw[$c] = $w; $wc[$w] = $c;
    }
    return true;
}

Time: O(n) | Space: O(n)

---

Q14 — First Missing Positive

🧠 How to Approach This

Step 1 — Recognize the pattern: Use array indices as a hash; place each num at index num-1.

Step 2 — Brute force (what NOT to do): Sort + linear scan — O(n log n).

Step 3 — Optimal insight: Cyclic sort: put 1→index 0, 2→index 1...; first mismatch = answer.

Step 4 — Algorithm:

1. Place each n in [1..n] at correct index

2. Scan: first i where nums[i] ≠ i+1 → return i+1

Step 5 — Edge cases: [1,2,3] → 4; [7,8,9] → 1.

function firstMissingPositive(array $nums): int {
    $n = count($nums);
    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]];
    }
    for ($i = 0; $i < $n; $i++) if ($nums[$i] !== $i + 1) return $i + 1;
    return $n + 1;
}

Time: O(n) | Space: O(1)

---

Q15 — Minimum Window Substring

🧠 How to Approach This

Step 1 — Recognize the pattern: Sliding window with frequency maps; expand right, shrink left.

Step 2 — Brute force (what NOT to do): Try all substrings — O(n² · m).

Step 3 — Optimal insight: Two pointers; formed counter tracks how many chars are satisfied.

Step 4 — Algorithm:

1. Build need map from t; expand r; when all formed → shrink l; track min window

Step 5 — Edge cases: t longer than s → ""; t not in s → "".

function minWindow(string $s, string $t): string {
    if (strlen($t) > strlen($s)) return '';
    $need = []; $have = []; $required = 0; $formed = 0;
    for ($i = 0; $i < strlen($t); $i++) $need[$t[$i]] = ($need[$t[$i]] ?? 0) + 1;
    $required = count($need);
    $l = 0; $minLen = PHP_INT_MAX; $res = '';
    for ($r = 0; $r < strlen($s); $r++) {
        $c = $s[$r]; $have[$c] = ($have[$c] ?? 0) + 1;
        if (isset($need[$c]) && $have[$c] === $need[$c]) $formed++;
        while ($formed === $required) {
            if ($r - $l + 1 < $minLen) { $minLen = $r - $l + 1; $res = substr($s, $l, $minLen); }
            $lc = $s[$l]; $have[$lc]--;
            if (isset($need[$lc]) && $have[$lc] < $need[$lc]) $formed--;
            $l++;
        }
    }
    return $res;
}

Time: O(n + m) | Space: O(n + m)

---

Q16 — Find All Anagrams in a String

🧠 How to Approach This

Step 1 — Recognize the pattern: Fixed-size sliding window matching frequency map.

Step 2 — Brute force (what NOT to do): Sort every window — O(n · k log k).

Step 3 — Optimal insight: Slide window of size p; maintain matched counter for O(1) window comparison.

Step 4 — Algorithm:

1. Init freq maps for first window

2. Slide: update right char (add), left char (remove), check matched === need count

Step 5 — Edge cases: p longer than s → [].

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; }
    $matched=0;
    foreach($need as $c=>$cnt) if(($have[$c]??0)===$cnt) $matched++;
    if($matched===count($need)) $result[]=0;
    for($i=strlen($p);$i<strlen($s);$i++){
        $r=$s[$i]; $have[$r]=($have[$r]??0)+1;
        if(isset($need[$r])){ if($have[$r]===$need[$r]) $matched++; elseif($have[$r]===$need[$r]+1) $matched--; }
        $l=$s[$i-strlen($p)]; $have[$l]--;
        if(isset($need[$l])){ if($have[$l]===$need[$l]) $matched++; elseif($have[$l]===$need[$l]-1) $matched--; }
        if($matched===count($need)) $result[]=$i-strlen($p)+1;
    }
    return $result;
}

Time: O(n) | Space: O(1)

---

Q17 — Ransom Note

🧠 How to Approach This

Step 1 — Recognize the pattern: Frequency map — magazine must have enough of each char.

Step 2 — Brute force (what NOT to do): For each char in note, scan magazine — O(n·m).

Step 3 — Optimal insight: Count magazine chars; verify note can be satisfied.

Step 4 — Algorithm:

1. Build freq map from magazine

2. For each char in ransomNote: if freq[c] < 1 → false; else decrement

Step 5 — Edge cases: Empty ransomNote → true.

function canConstruct(string $ransomNote, string $magazine): bool {
    $freq = [];
    for ($i = 0; $i < strlen($magazine); $i++) $freq[$magazine[$i]] = ($freq[$magazine[$i]] ?? 0) + 1;
    for ($i = 0; $i < strlen($ransomNote); $i++) {
        $c = $ransomNote[$i];
        if (($freq[$c] ?? 0) < 1) return false;
        $freq[$c]--;
    }
    return true;
}

Time: O(n + m) | Space: O(1)

---

Q18 — Jewels and Stones

🧠 How to Approach This

Step 1 — Recognize the pattern: HashSet for jewel types; count stones that are jewels.

Step 2 — Brute force (what NOT to do): For each stone scan jewels string — O(n·m).

Step 3 — Optimal insight: HashSet from jewels for O(1) lookup.

Step 4 — Algorithm:

1. Build set from jewels

2. Count stones in set

Step 5 — Edge cases: Empty stones → 0.

function numJewelsInStones(string $jewels, string $stones): int {
    $set = []; $count = 0;
    for ($i = 0; $i < strlen($jewels); $i++) $set[$jewels[$i]] = true;
    for ($i = 0; $i < strlen($stones); $i++) if (isset($set[$stones[$i]])) $count++;
    return $count;
}

Time: O(j + s) | Space: O(j)

---

Q19 — Longest Palindrome from Characters

🧠 How to Approach This

Step 1 — Recognize the pattern: Frequency map; pairs contribute 2, at most one odd-count char in center.

Step 2 — Brute force (what NOT to do): Try all permutations.

Step 3 — Optimal insight: Sum all even frequencies + (odd-1) for each odd; add 1 if any odd exists.

Step 4 — Algorithm:

1. Count freq of each char

2. Sum += freq//2 * 2; if any freq is odd → canAddCenter = true

3. Return sum + (canAddCenter ? 1 : 0)

Step 5 — Edge cases: Single char → 1.

function longestPalindrome(string $s): int {
    $freq = []; $len = 0; $hasOdd = false;
    for ($i = 0; $i < strlen($s); $i++) $freq[$s[$i]] = ($freq[$s[$i]] ?? 0) + 1;
    foreach ($freq as $f) {
        $len += intdiv($f, 2) * 2;
        if ($f % 2 !== 0) $hasOdd = true;
    }
    return $len + ($hasOdd ? 1 : 0);
}

Time: O(n) | Space: O(1)

---

Q20 — Pairs with Given Difference

🧠 How to Approach This

Step 1 — Recognize the pattern: For each n, check if n+k exists in set.

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: HashSet; for each n check if n+k (or n-k) in set.

Step 4 — Algorithm:

1. Build set from nums

2. For each n: if n+k in set and n != n+k (when k=0) → count pair

3. Avoid duplicates

Step 5 — Edge cases: k=0 → duplicates within array; negative k.

function findPairs(array $nums, int $k): int {
    if ($k < 0) return 0;
    $freq = []; $count = 0;
    foreach ($nums as $n) $freq[$n] = ($freq[$n] ?? 0) + 1;
    foreach ($freq as $n => $f) {
        if ($k === 0) { if ($f > 1) $count++; }
        else if (isset($freq[$n + $k])) $count++;
    }
    return $count;
}

Time: O(n) | Space: O(n)

---

Q21 — Minimum Index Sum of Two Lists

🧠 How to Approach This

Step 1 — Recognize the pattern: Map first list index → element; scan second for matches.

Step 2 — Brute force (what NOT to do): Nested loops — O(n·m).

Step 3 — Optimal insight: Map list1 element → index; iterate list2 checking map; track min sum.

Step 4 — Algorithm:

1. Map list1: element → index

2. For each (j, item) in list2: if in map, compute i+j; update min; collect ties

Step 5 — Edge cases: Multiple pairs with same min sum.

function findRestaurant(array $list1, array $list2): array {
    $map = array_flip($list1); $minSum = PHP_INT_MAX; $result = [];
    foreach ($list2 as $j => $item) {
        if (isset($map[$item])) {
            $sum = $map[$item] + $j;
            if ($sum < $minSum) { $minSum = $sum; $result = [$item]; }
            elseif ($sum === $minSum) $result[] = $item;
        }
    }
    return $result;
}

Time: O(n + m) | Space: O(n)

---

Q22 — Custom Sort String

🧠 How to Approach This

Step 1 — Recognize the pattern: Frequency map of s; output chars in order defined by order string.

Step 2 — Brute force (what NOT to do): Custom comparator sort — O(n log n).

Step 3 — Optimal insight: Count freq of s; output in order string first, then remaining.

Step 4 — Algorithm:

1. Build freq map of s

2. For each char in order: append freq[c] times; unset

3. Append remaining chars

Step 5 — Edge cases: Chars in s not in order.

function customSortString(string $order, string $s): string {
    $freq = [];
    for ($i = 0; $i < strlen($s); $i++) $freq[$s[$i]] = ($freq[$s[$i]] ?? 0) + 1;
    $result = '';
    for ($i = 0; $i < strlen($order); $i++) {
        $c = $order[$i];
        if (isset($freq[$c])) { $result .= str_repeat($c, $freq[$c]); unset($freq[$c]); }
    }
    foreach ($freq as $c => $f) $result .= str_repeat($c, $f);
    return $result;
}

Time: O(n) | Space: O(n)

---

Q23 — Count Pairs Divisible by K

🧠 How to Approach This

Step 1 — Recognize the pattern: Remainder map — (a+b) % k === 0 when rem[a] + rem[b] === k.

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: For each n, check if k - (n%k) remainder exists in map.

Step 4 — Algorithm:

1. For each n: need = (k - n%k) % k; count += remMap[need] ?? 0

2. Then add n%k to remMap

Step 5 — Edge cases: n%k=0 → need 0 remainder partner; k=1 → all pairs.

function countPairs(array $nums, int $k): int {
    $remMap = []; $count = 0;
    foreach ($nums as $n) {
        $rem  = $n % $k;
        $need = ($k - $rem) % $k;
        $count += $remMap[$need] ?? 0;
        $remMap[$rem] = ($remMap[$rem] ?? 0) + 1;
    }
    return $count;
}

Time: O(n) | Space: O(k)

---

Q24 — Number of Boomerangs

🧠 How to Approach This

Step 1 — Recognize the pattern: For each point, count others at same distance; permutations of pairs.

Step 2 — Brute force (what NOT to do): Triple nested loop — O(n³).

Step 3 — Optimal insight: For each anchor point, build distance frequency map; count = sum(f*(f-1)).

Step 4 — Algorithm:

1. For each point as anchor: build dist→count map

2. For each dist with f occurrences: count += f*(f-1) (ordered pairs)

Step 5 — Edge cases: n < 3 → 0.

function numberOfBoomerangs(array $points): int {
    $count = 0;
    foreach ($points as $p) {
        $distMap = [];
        foreach ($points as $q) {
            $d = ($p[0]-$q[0])**2 + ($p[1]-$q[1])**2;
            $distMap[$d] = ($distMap[$d] ?? 0) + 1;
        }
        foreach ($distMap as $f) $count += $f * ($f - 1);
    }
    return $count;
}

Time: O(n²) | Space: O(n)

---

Q25 — Longest Subarray with Sum Divisible by K

🧠 How to Approach This

Step 1 — Recognize the pattern: Prefix sum modulo k; same remainder at two indices means divisible subarray.

Step 2 — Brute force (what NOT to do): Check all subarrays — O(n²).

Step 3 — Optimal insight: Map of first occurrence of each remainder; max length = i - remMap[rem].

Step 4 — Algorithm:

1. remMap[0] = -1; running sum %= k (normalize negative)

2. If rem seen → max(best, i - remMap[rem]); else remMap[rem] = i

Step 5 — Edge cases: Negative numbers; no valid subarray → 0.

function subarraysDivByK(array $nums, int $k): int {
    $remMap = [0 => -1]; $sum = 0; $best = 0;
    foreach ($nums as $i => $n) {
        $sum += $n;
        $rem = (($sum % $k) + $k) % $k; // normalize negative remainders
        if (isset($remMap[$rem])) $best = max($best, $i - $remMap[$rem]);
        else $remMap[$rem] = $i;
    }
    return $best;
}

Time: O(n) | Space: O(k)