When to use arrays

• When you need order
• When you need fast access / insertion and removal

Big O of Arrays

Insertion - It depends... O(N) when inserting at the beginning

Removal - It depends... O(N) when removing from the beginning

Searching - O(N)

Access - O(1)

Big O of Array Operations

push - O(1)

pop - O(1)

shift - O(N)

unshift - O(N)

concat - O(N)

slice - O(N)

splice - O(N)

sort - O(N*logN)

forEach/map/filter/reduce/etc. - O(N)

const strings= ['a', 'b', 'c', 'd'];
const numbers = [1,2,3,4,5];
// Variable array is somewhere in memory and the computer knows it.
// When I do array[2], i'm telling the computer, hey go to the array and grab the 3rd item from where the array is stored.


//push
strings.push('e');

//pop
strings.pop();
strings.pop();

//unshift
strings.unshift('x')

//splice
strings.splice(2, 0, 'alien');

console.log(strings)

Linear Search

If the index is not known, which is the case most of the time, then we can check every element in the Array. We continue checking elements until we find the element we're looking for, or we reach the end of the Array. This technique for finding an element by checking through all elements one by one is known as the linear search algorithm.

In the worst case, a linear search ends up checking the entire Array. Therefore, the time complexity for a linear search is O(N).

Binary Search

There is another way of searching an Array. If the elements in the Array are in sorted order, then we can use binary search. Binary search is where we repeatedly look at the middle element in the Array, and determine whether the element we're looking for must be to the left, or to the right. Each time we do this, we're able to halve the number of elements we still need to search, making binary search a lot faster than linear search!

The downside of binary search though is that it only works if the data is sorted. If we only need to perform a single search, then it's faster to just do a linear search, as it takes longer to sort than to linear search. If we're going to be performing a lot of searches, it is often worth sorting the data first so that we can use binary search for the repeated searches.

In-Place Array Operations

In programming interviews, the interviewer often expects you to minimize the time and space complexity of your implementation. In-place Array operations help to reduce space complexity, and so are a class of techniques that pretty much everybody encounters regularly in interviews.

An important difference for in-place vs not in-place is that in-place modifies the input Array. This means that other functions can no longer access the original data, because it has been overwritten.