Introduction

• 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
• different programming languages implement arrays under the hood differently and can affect the time complexity of operations you make to the array
  • in some languages like Python, JavaScript, Ruby, PHP, the array (or list in Python) size is dynamic and you do not need to have a size defined beforehand when creating the array, as a result, people usually have an easier time using these languages for interviews

Advantages

• store multiple elements of the same type with one single variable name
• Accessing elements is fast as long as you have the index, as opposed to linked lists where you have to traverse from the head

Disadvantages

• Addition and Removal of elements into/from the middle of an array is slow 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
• For certain languages where the array size is fixed, 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.

Elements

Subarray

• a range of contiguous values within an array

e.g. 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

e.g. given an array [2, 3, 6, 1, 5, 4], [3, 1, 5] is a subsequence but [3, 5, 1] is not a subsequence

Types

Static Array