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