Let's start by defining an array. An array is a data structure that organise elements in a particular order under a single name. We can access them by its index
For example if you have a bunch of test scores, rather storing them using different variable names, we use array which gives us more organisation and ease in iteration specially when the scores are changing. They keep all the values in a sequence. We can change the order of the elements by performing certain operations on the array.
Let's say we have scores: [12, 16, 18, 20, 23]
We’ll use zero-based indexing: an array of length n has indices from 0 to n − 1.
To read any value in an array, we just need to know its index and we can get its value in a constant time. The time complexity to get a value is O(1)
For our example we have ‘18’ at index ‘2’
scores[2] → 18One indexed accessSelect any cell. Its index identifies the position; the number inside is the value.
Although if you don't know the position and you just know the value, these are two different things. To know the position of a certain value, one of the ways is to start from index 0 and move forward. As we move forward we just check each element and see if it matches the value we are tring to find. It's called linear search.
The time complexity in this case increases since we don't know the position and the worst case here is that we have to check through all the elements to get our value. Hence the time complexity here is O(n)
Start at index 0. No comparisons yet.
Choose 99 to try an unsuccessful search. Even though these example values are sorted, this walkthrough uses linear search.
There are two types of arrays in terms of sizes: fixed-size arrays and dynamic arrays
A dynamic array is useful when you don't know if you have a fixed number of elements to fill in. If you run out of room it automatically creates a bigger block and create copies of every existing element across.
A dynamic array has a length (the number of elements it holds) and a capacity (the number of elements it can hold before it needs more space). When we append more than the capacity it requires more capacity before the new element can be added
When that happens, a common strategy is to double the capacity. A copy of the existing array is copied into to new bigger array. This copy takes time O(n). Across a sequence of appends starting from an empty array, the cost per append is O(1) amortized.
Five elements fill five slots. Appending 31 needs more room.
This example doubles capacity. Copying five existing elements takes five copy operations; unused slots are capacity, not additional elements.
We can insert, delete elements in an array (in a dynamic array). Inserting and deleting are expensive operations. If you have to insert or delete an element at the start of an array, let's say you have to put a number at the beginning, every other number after that has to shift by one place, which makes it expensive. In the same way if you delete something, every position after that has to shift leftwards by one place. Although if you are adding or deleting something from the end of the array, it's pretty cheap because you don't need to shift anything
Insert 9 at index 0. Start shifting from the right so no value is overwritten.
An empty cell marks a spare or temporarily vacant slot. The arrows show which value moved in the current step.
| Operation | Complexity | Why |
|---|---|---|
| Access by index | O(1) | Position is computed directly |
| Update by index | O(1) | Overwrites in place |
| Search by value | O(n) | Might have to check everything |
| Insert / delete at end | O(1) amortised | Nothing shifts |
| Insert / delete at start or middle | O(n) | Everything after it shifts |
Some questions that you might face while solving array problems could be:
- concatenation of arrays
- shuffling the arrays
- finding maximum consecutive same elements in an array