Array Cheatsheet
Arrays
Arrays hold values of the same type at contiguous memory locations. In an array, we're usually concerned about two things - the position/index of an element and the element itself.
Advantages
- Store multiple elements of the same type with one single variable name
- Accessing elements is fast (o(1)) as long as you have the index, as opposed to linked lists where you have to traverse from the head (o(n)).
Disadvantages
- Addition and removal of elements in the middle of an array is slow (o(n)) because the remaining elements need to be shifted to accommodate the new/missing element.
- An exception to this is if the position to be inserted/removed is at the end of the array (o(1)).
- It cannot alter its size after initialization.
- If an insertion causes the total number of elements to exceed the size, a new array has to be allocated and the existing elements have to be copied over.
- The act of creating a new array and transferring elements over takes O(n) time.
Common terms
- Subarray - A range of contiguous values within an array.
- Example: given an array
[2, 3, 6, 1, 5, 4],[3, 6, 1]is a subarray while[3, 1, 5]is not a subarray.
- Example: given an array
- Subsequence - A sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.
- Example: given an array
[2, 3, 6, 1, 5, 4],[3, 1, 5]is a subsequence but[3, 5, 1]is not a subsequence.
- Example: given an array
Things to look out for during interviews
- Clarify if there are duplicate values in the array. Would the presence of duplicate values affect the answer? Does it make the question simpler or harder?
- When using an index to iterate through array elements, be careful not to go out of bounds.
- Be mindful about slicing or concatenating arrays in your code. Typically, slicing and concatenating arrays would take O(n) time. Use start and end indices to demarcate a subarray/range where possible.
Corner Cases
- Empty sequence
- Sequence with 1 or 2 elements
- Sequence with repeated elements
- Duplicated values in the sequence
Time Complexity
| Operation | Big-O | Note |
|---|---|---|
| Access | O(1) | |
| Search | O(n) | |
| Search (sorted array) | O(log(n)) | |
| Insert | O(n) | Insertion would require shifting all the subsequent elements to the right by one and that takes O(n) |
| Insert (at the end) | O(1) | Special case of insertion where no other element needs to be shifted |
| Remove | O(n) | Removal would require shifting all the subsequent elements to the left by one and that takes O(n) |
| Remove (at the end) | O(1) | Special case of removal where no other element needs to be |
Resource
Array in Data Structure: What is, Arrays Operations [Examples]