Arrays & Hashing

What is the main idea of hashing problems?

Use a hash structure (set or map) to get O(1) average lookup instead of scanning the array

General hashing problem skeleton

"Initialize hash structure → iterate → check condition → update hash → return result"

Python HashSet creation

set() or set(nums)

Python HashMap creation

{} or dict()

Python frequency map template

"from collections import defaultdict\nfreq = defaultdict(int)\nfor x in nums:\n freq[x] += 1"

Python Counter usage

"from collections import Counter\nfreq = Counter(nums)"

When should you use a HashSet?

When you only care about existence and uniqueness

When should you use a HashMap?

When you need key → value relationships

Time complexity of HashSet operations

Average O(1) lookup insert delete

Worst case time complexity of HashSet operations

O(n) due to collisions

Time complexity of HashMap operations

Average O(1)

Worst case time complexity of HashMap operations

O(n)

Space complexity of hashing problems

O(n)

LC 217 – Contains Duplicate: check if any value appears twice

Pattern: HashSet — store seen elements and check membership

LC 242 – Valid Anagram: check if two strings have same character counts

Pattern: Frequency HashMap or Counter

LC 1 – Two Sum: find two numbers that add up to target

Pattern: HashMap — store complement

LC 49 – Group Anagrams: group words with same character frequency

Pattern: HashMap with sorted string or frequency tuple as key

LC 347 – Top K Frequent Elements: return k most frequent values

Pattern: HashMap + Heap or Bucket Sort

LC 238 – Product of Array Except Self: multiply all except self without division

Pattern: Prefix + Suffix arrays

LC 36 – Valid Sudoku: check if rows columns and boxes are valid

Pattern: HashSet tracking

LC 128 – Longest Consecutive Sequence: find longest run of consecutive numbers

Pattern: HashSet + greedy expansion

How does Two Sum hashing logic work?

For each num check if target-num exists in map else store num:index

Two Sum Python template

"seen = {}\nfor i

Valid Anagram Python template

"from collections import Counter\nreturn Counter(s) == Counter(t)"

Contains Duplicate Python template

"seen = set()\nfor n in nums:\n if n in seen: return True\n seen.add(n)\nreturn False"

Group Anagrams Python template

"from collections import defaultdict\ngroups = defaultdict(list)\nfor s in strs:\n key = ''.join(sorted(s))\n groups[key].append(s)\nreturn list(groups.values())"

Product Except Self idea

Prefix product * Suffix product

Product Except Self Python template

"res = [1]*n\nprefix = 1\nfor i in range(n):\n res[i] = prefix\n prefix *= nums[i]\nsuffix = 1\nfor i in range(n-1

Longest Consecutive core idea

Start only from numbers that have no left neighbor

Longest Consecutive Python template

"numSet = set(nums)\nlongest = 0\nfor n in numSet:\n if n-1 not in numSet:\n length = 1\n while n+length in numSet:\n length += 1\n longest = max(longest

Valid Sudoku checking idea

Use 3 hash sets: rows cols boxes

Valid Sudoku Python structure

"rows = [set() for _ in range(9)]\ncols = [set() for _ in range(9)]\nboxes = [set() for _ in range(9)]"

What is the biggest advantage of hashing?

Constant time lookups

Common mistake in hashing problems

Forgetting to update the hash after checking

Common mistake in Two Sum

Storing before checking

Common mistake in frequency problems

Not initializing counts correctly

How do you avoid KeyError in Python dict?

Use get() or defaultdict

dict.get() usage

dict.get(key

defaultdict benefit

Automatically initializes missing keys

When NOT to use hashing?

When order matters or memory is constrained

How do you check membership in O(1)?

Using a set

How do you track frequency?

Using a dictionary or Counter

Why is hashing good for duplicate detection?

Fast existence checking

Key idea of Group Anagrams

Same frequency signature

Key idea of Longest Consecutive

Only start sequences from valid starts

Key idea of Product Except Self

Prefix and suffix multiplication