# Arrays & Hashing — Part 2: Interview Problems

Six classic problems in increasing difficulty. Try each one for 15–20 minutes before reading the approach.

## 1. Contains Duplicate (LeetCode 217)

**🟢 Easy.** Return `true` if any value appears at least twice in `nums`, otherwise `false`.

```text
nums = [1,2,3,1] → true
nums = [1,2,3,4] → false
```

**Approach.** Insert each number into a set; if it's already there, you've found a duplicate. (Sorting and comparing neighbours also works in O(n log n) time and O(1) extra space.)

**Complexity.** O(n) time, O(n) space.

```typescript
function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}
```

```python
def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False
```

## 2. Valid Anagram (LeetCode 242)

**🟢 Easy.** Given strings `s` and `t`, return `true` if `t` is an anagram of `s` (same letters, same counts).

```text
s = "anagram", t = "nagaram" → true
```

**Approach.** Different lengths → false immediately. Otherwise count letters of `s` up and letters of `t` down; every count must end at zero.

**Complexity.** O(n) time, O(1) space for a fixed alphabet (O(k) for k distinct characters).

```typescript
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const counts = new Map<string, number>();
  for (let i = 0; i < s.length; i++) {
    counts.set(s[i], (counts.get(s[i]) ?? 0) + 1);
    counts.set(t[i], (counts.get(t[i]) ?? 0) - 1);
  }
  for (const v of counts.values()) if (v !== 0) return false;
  return true;
}
```

```python
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    counts = {}
    for a, b in zip(s, t):
        counts[a] = counts.get(a, 0) + 1
        counts[b] = counts.get(b, 0) - 1
    return all(v == 0 for v in counts.values())
```

## 3. Group Anagrams (LeetCode 49)

**🟠 Medium.** Group the strings in `strs` so that anagrams are together. Any order is accepted.

```text
strs = ["eat","tea","tan","ate","nat","bat"]
→ [["bat"],["nat","tan"],["ate","eat","tea"]]
```

**Approach.** Use a canonical key per word. Sorting the letters gives O(k log k) per word; a 26-slot count tuple gives O(k). Append each word to the bucket for its key.

**Complexity.** O(n·k) time with count keys, O(n·k) space.

```typescript
function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of strs) {
    const counts = new Array(26).fill(0);
    for (const c of w) counts[c.charCodeAt(0) - 97]++;
    const key = counts.join("#");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(w);
  }
  return [...groups.values()];
}
```

```python
from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for w in strs:
        counts = [0] * 26
        for c in w:
            counts[ord(c) - 97] += 1
        groups[tuple(counts)].append(w)
    return list(groups.values())
```

## 4. Top K Frequent Elements (LeetCode 347)

**🟠 Medium.** Return the `k` most frequent elements of `nums`. The answer is unique; any order.

```text
nums = [1,1,1,2,2,3], k = 2 → [1,2]
```

**Approach.** Count frequencies, then **bucket sort by frequency**: `buckets[f]` holds the numbers that occur f times (f ≤ n). Walk buckets from high to low until you have k numbers. A size-k heap gives O(n log k) and is the more general answer; buckets give O(n).

**Complexity.** O(n) time with buckets, O(n) space.

```typescript
function topKFrequent(nums: number[], k: number): number[] {
  const counts = new Map<number, number>();
  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [x, f] of counts) buckets[f].push(x);
  const result: number[] = [];
  for (let f = buckets.length - 1; f > 0 && result.length < k; f--) {
    for (const x of buckets[f]) {
      result.push(x);
      if (result.length === k) break;
    }
  }
  return result;
}
```

```python
def top_k_frequent(nums, k):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]
    for x, f in counts.items():
        buckets[f].append(x)
    result = []
    for f in range(len(buckets) - 1, 0, -1):
        for x in buckets[f]:
            result.append(x)
            if len(result) == k:
                return result
    return result
```

## 5. Product of Array Except Self (LeetCode 238)

**🟠 Medium.** Return `answer` where `answer[i]` is the product of all elements except `nums[i]`, in O(n) time **without division**.

```text
nums = [1,2,3,4] → [24,12,8,6]
```

**Approach.** `answer[i]` = (product of everything left of i) × (product of everything right of i). First pass left→right writes the prefix products into `answer`; second pass right→left multiplies in a running suffix product.

**Complexity.** O(n) time, O(1) extra space (the output array doesn't count).

```typescript
function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) { answer[i] = prefix; prefix *= nums[i]; }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) { answer[i] *= suffix; suffix *= nums[i]; }
  return answer;
}
```

```python
def product_except_self(nums):
    n = len(nums)
    answer = [1] * n
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]
    return answer
```

## 6. Longest Consecutive Sequence (LeetCode 128)

**🟠 Medium.** Return the length of the longest run of consecutive integers in an unsorted array, in O(n) time.

```text
nums = [100,4,200,1,3,2] → 4   (1,2,3,4)
```

**Approach.** Put everything in a set. A number starts a run only if `x − 1` is **not** in the set; from each start, count upward while `x + 1` exists. Every number is visited at most twice (once as a candidate, once inside a run), so the total is O(n), even though there's a nested loop.

**Complexity.** O(n) time, O(n) space.

```typescript
function longestConsecutive(nums: number[]): number {
  const s = new Set(nums);
  let best = 0;
  for (const x of s) {
    if (s.has(x - 1)) continue;          // not a run start
    let length = 1;
    while (s.has(x + length)) length++;
    best = Math.max(best, length);
  }
  return best;
}
```

```python
def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:              # x starts a run
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best
```