Arrays are a way to store data contiguously.
In strictly typed languages, such as C++, Java or C#, arrays have to have an allocated size when initialized; loosely typed languages like JavaScript or Python do not have static arrays.
Dynamic arrays are resized automatically by the operating system. When inserting into an array, the operating system finds the next available slot and inserts the item into this slot. If there is no slot available (we are exceeding the array capacity), adding a new element is achieved by copying all elements of the first array into an array that is double its size, assign this to a new address in memory and removing the reference to the previous array in memory.
Advantages
- Store multiple elements with a single variable name
- Accessing elements is fast as long as you have the index
Disadvantages
- Addition and removal of elements in/from the middle of the array is slow because the rest of the elements need to be shifted to accommodate the new/missing element.
Operations
| Operation | Complexity |
|---|---|
| Read / write [i] element | O(1) |
| Insert / remove at the end | O(1) |
| Insert in the middle | O(n) |
| Remove in the middle | O(n) |
Techniques
-
Sliding window
In a sliding window, the two pointers usually move in the same direction will never overtake each other.
This ensures that each value is only visited at most twice and the time complexity is still O(n)
-
Two pointers
Two pointers is a more general version of sliding window where the pointers can cross each other and can be on different arrays.
-
Traversing from the right
-
Sorting the array
-
Index as a hash key
-
Traversing the array more than once