Array and Hashing

Writing this at 11pm.

I’m so tired..

Keywords and Patterns

Anything that involves repetition, keeping track, counts, copying, generally requires hashmaps one way or another.

Examples

Duplicates and Frequencies

Checking for duplicates

 
hashmaps = set()
 
for num in nums:
    if num in hashmap:
        return True
    hashmaps.add(num)
 
 
return False

You can modify the code above to keep track of the frequency of each element

 
hashmap = {}
for num in nums:
    if num in hashmaps:
        hashmap[num] = hashmap.get(num, 0) + 1
    hashmap.get(num,0)

or, you can simply

from collections import Counter
 
hashmap = Counter(num)

Clones

Generally, cloning uses hashmap where the key of the hashmap is the original node/data and the value is the clone.

this uses copy list with random pointer as an example

mapping = defaultdict(lambda: Node(0))
 
while curr:
    mapping[curr].val = curr.val
    mapping[curr].next = curr.next
    mapping[curr].random = mapping[curr.random]
    curr = curr.next
return mapping[head]

A two pass version is also possible; you just have to populate the hashmap with nodes (both key and value) beforehand.

Some other tips and tricks

The index of an array can also be used to solve a problem. Take this problem for example,

Source: find the duplicate number

Solve the problem before opening this!

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

The problem introduced a very specific constraint integer is in the range [1, n]; this means that every number in the array is a valid index of the array.

Problems:

• Contains Duplicate
• Valid Anagram