# 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[​](https://www.techinterviewhandbook.org/algorithms/array/#common-terms "Direct link to 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.
- 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.

#### Things to look out for during interviews[​](https://www.techinterviewhandbook.org/algorithms/array/#things-to-look-out-for-during-interviews "Direct link to 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[​](https://www.techinterviewhandbook.org/algorithms/array/#corner-cases "Direct link to Corner cases")

- Empty sequence
- Sequence with 1 or 2 elements
- Sequence with repeated elements
- Duplicated values in the sequence

#### Time Complexity[​](https://www.techinterviewhandbook.org/algorithms/array/#corner-cases "Direct link to Corner cases")

<table id="bkmrk-operation-big-o-note"><thead><tr><th>Operation</th><th>Big-O</th><th>Note</th></tr></thead><tbody><tr><td>Access</td><td>O(1)</td><td> </td></tr><tr><td>Search</td><td>O(n)</td><td> </td></tr><tr><td>Search (sorted array)</td><td>O(log(n))</td><td> </td></tr><tr><td>Insert</td><td>O(n)</td><td>Insertion would require shifting all the subsequent elements to the right by one and that takes O(n)</td></tr><tr><td>Insert (at the end)</td><td>O(1)</td><td>Special case of insertion where no other element needs to be shifted</td></tr><tr><td>Remove</td><td>O(n)</td><td>Removal would require shifting all the subsequent elements to the left by one and that takes O(n)</td></tr><tr><td>Remove (at the end)</td><td>O(1)</td><td>Special case of removal where no other element needs to be</td></tr></tbody></table>

Resource

[Array in Data Structure: What is, Arrays Operations \[Examples\]](https://www.guru99.com/array-data-structure.html)