# 12. Arrays & Hashing

## A. General Introduction

Set is implemented as a hash table in python.

**Average case:** Lookup/insert/delete = O(1)

**Worst case:** Lookup/insert/delete = O(n); due to hash collision

## B. Leetcode problems

### 128. Longest Consecutive Sequence

Given an unsorted array of integers `nums`

, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in `O(n)`

time.

Example:

Input:nums = [100,4,200,1,3,2]

Output:4Explanation:The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

#### Key ideas:

- What determines a sequence is the start and end, so create a set and check if the
`num-1`

exists in the set- If it does not exist, then it is the start of a sequence
- iteratively increase the length of the sequence till the num is not in the set
- check max length

- If it does not exist, then it is the start of a sequence

## code

```
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
history = set(nums)
maxlen = float("-inf")
for num in nums:
if num-1 not in history:
# start of a sequence
length = 0
while (num+length) in history:
length += 1
maxlen = max(maxlen, length)
return maxlen
```

### 1. Two Sum

Given an array of integers `nums`

and an integer `target`

, return *indices of the two numbers such that they add up to target.*

You may assume that each input would have **exactly one solution**, and you may not use the *same element twice.*

You can return the answer in any order.

Example:

Input:nums = [2, 7, 11, 15], target = 9

Output:[0, 1]

Explanation:Because nums[0] + nums[1] == 9, we return [0, 1].

#### Key Ideas:

- Use a hash table to store the number and its index
- Iterate through the array and check if the number is in the hash table
- If it is, return the index pair
- If it is not, then add the difference between the number and target to the hash table with the index

## code

```
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i, val in enumerate(nums):
if val in hashmap:
return [hashmap[val], i]
hashmap[target-val] = i
return -1
```