Intro

An array is a basic data structure to store elements sequentially (generally in a contiguous area of memory). Elements can be accessed randomly since each element can be retrieved using an index.

Arrays have fixed capacity, programming languages give the illusion of variable arrays by reallocating and moving the elements.

Interesting facts:

• In C++ multidimensional arrays are contiguous while in Java, each dimension is kept in a separate array indexed by a base array.

• String are arrays of unicode characters. In C++ and JAVA they are immutable (stringBuilder is based on char[]). Moreover, they only support == if the the language supports operator overloading (C++ yes, java no)

• Example: Maximum Consecutive Ones

Insertion => O(n)

Inserting may require shifting all the other elements which is an operation proportional to the length.

Linear Search => O(n)

If we check each element of the array to find the index of the element we are looking for we are performing a linear search. In the worst case we have to search through all the elements: => O(n).

There are several better search algorithms that can take advantage of sorted arrays to find a specific index faster.

In Place Operations

In place operations are operations that minimize space complexity by working directly on the input array.