##

Arrays are contiguous

An array stores data sequentially, usually starting at 0 based index

Linear array or one dimensional array, static in size

Dynamic array and hash map are built on array

Fixed-size, elements located by index or address

Strengths:

  1. constant-time access
  2. space efficiency
  3. memory locality

Weaknesses:

  1. fixed size
  2. costly inserts and deletes

Rotated array simply means an array that has shifted to the right or left by a number of steps, the element from one end will move to the other end

Runtime Complexity

lookup \(O(1)\) fast lookup append \(O(1)\) fast append insert \(O(n)\) delete \(O(n)\)

Space Complexity

\[O(n)\]

Dynamic Arrays

If a dynamic array is full, it copies its content to a larger array

std::vector

Multidimensional Arrays

Multidimensional arrays are simply nested arrays that allow for multiple dimensions

Two Dimensional Array

Three Dimensional Array

Strings

Strings and arrays are often interchangeable