Arrays and Hashing

Problems

#	Problem	Difficulty	Hint	Tags
217	Contains Duplicate	Easy	Hint What data structure can we use here to keep track of unique elements?	#array #hashtable #sorting
242	Valid Anagram	Easy	Hint How do we keep track of the count of letters? What is an optimal data structure?	#hashtable #string #sorting
1	Two Sum	Easy	Hint What data structure can we use to keep track of numbers we have already seen? What's the condition for returning the 2 indices?	#array #hashtable
62	Group Anagrams	Medium	Hint Which data structure can you use to store what string goes where? What is the key of this data structure?	#array #hashtable #string #sorting
374	Top K Frequent Elements	Medium	Hint What data structure can you use to store the counts of each number? Then, what data structure can you use to keep track of only the top k elements?	#array #hashtable #divideandconquer #sorting #heap #bucketsort #counting #quickselect
238	Product of Array Except Self	Medium	Hint Think about how we can use prefix and suffix products. Think about how we can use 2 passes to get our answer.	#array #prefixsum
36	Valid Sudoku	Medium	Hint What data structure can you use to keep track of the numbers seen in each row, column and box? How can you represent the boxes in this data structure?	#array #hashtable #matrix
128	Longest Consecutive Sequence	Medium	Hint We only need to consider elements that start a sequence and count from there. What data structure do we use for O(1) lookups?	#array #hashtable #unionfind

Dynamic Arrays

Dynamic arrays are arrays that can resize themselves automatically during program execution. Python arrays are dynamic arrays.

Common array terms

Subarray - a range of contiguous values
Subsequence - a sequence that can be derived from an array while deleting some or no values and without changing the order.

Techniques

Hashing

Python has two data structures that rely on hashing and are quite useful for solving many different problems.

A dictionary in Python is a data structure which can be used to store key value pairs. It is declared using dict = {} (curly braces). This is best used when you need to a quick O(1) look up of a specific value.

Note: You can make a set or an array a key in dict by turning into a tuple.

Note: As of Python 3.7, dictionaries in Python are ordered.

A set is a collection of unique items. Checking whether an item is in the set takes O(1) time but actually getting a specific item from the set takes O(n) time. You can make a set in Python using my_set = set(). This is best used when you need to keep track of distinct items.

We can also use an array as an hash map if we know that the index of the array will serve as the key. For example, using an array to index the alphabet ([0] * 26). For example, this could keep track of the count of each character in the alphabet.

Tips and Tricks

Calculate the unicode number of character using ord('c').
To get the alphabet position of lowercase letter ord('char') - ord('a).
defaultdict(type) is used to create a dict with many keys that share the same default value.
To use a list as a key in a dict in, turn into a tuple using tuple(list).
Getting count of elements in an array:

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

Array splicing is done by sequence[start:stop:step]
Use the method setdefault(key, value) on a dictionary to create a key with the specified value if the key doesn't exist but don't change the value if the key already exists.
.split(separator, maxsplit) separates a string based on a delimiter a max number of times. My default, separator is whitespace and maxsplit is -1 which is all occurrences.