# Arrays

Arrays are like buckets that hold values.

## Intro

Store value of different type (in JS) at contiguous memory location. Strings are arrays as well.

### Advantages

- Fast access if you have index

### Disadvantages

- Adding or removal from the middle is slow, opposed to Linked List.

## Terms

- Subarray, [1,4,5,2] -> [4,5,2] is a subarray
- Subsequence, [1,4,5,2] -> [1,4,2] is a subsequence

The difference is that a subarray can't have any element in between, it has to be contiguous. A subsequence can be derived from the original array by deleting elements, but the order has to stay the same

## Time Complexity

- Access: O(1)
- Search: O(n)
- Search sorted: O(log n)
- Insert: O(n)
- Insert at the end (.push()): O(1)
- Remove: O(n)
- Remove at the end (.pop()): O(1)

## Look out for in interview

- Are there duplicates in the array? Would this affect the answer?
- Remember the bounds when using indexes
- .slice() and .concat() need O(n) time, prefer subarray

## Corner Cases

- Empty sequence
- Duplicates
- Sequence with repeated elements
- Sequence with 1 or 2 elements

## Techniques

Sliding Window - Subarray / Substring

Two Pointers