Arrays | Skilled.dev
Learn

Arrays

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

Arrays are a simple and intuitive data structure. We use them when we have a list of sequential items and want to iterate over the items one-by-one. These items are also stored contiguously in memory. We use numerical indexes to access items in the array which operate in constant O(1) time.

We will typically assume we're using a dynamic array unless specified otherwise. A dynamic array means that it can change size during the lifetime of your program - you can continue to add items and let the list grow to an arbitrary size. In an upcoming section, we'll compare dynamic arrays to static arrays where the size must be set when the array is declared.

Cheat Sheet

Common names: array, list, dynamic array, static array, matrix

0"Facebook"
1"Amazon"
2"Apple"
3"Netflix"
4"Google"
5"Skilled.dev"
6"gitconnected"
Big O Complexity
lookupO(1)
setO(1)
search (unsorted)O(n)
search (sorted)O(log n)
insertO(n)
deleteO(n)
appendO(1)
prependO(n)
spaceO(n)
Pros 🔥
  • Ordered
    Arrays are sequentially ordered and index the location of items
  • Fast lookups
    You can get/set an item at an index in constant O(1) time
  • Fast push / pop
    Adding and removing the last item is fast
  • Represent a matrix
    You can nest arrays to represent higher-order data
Cons 🤕
  • Slow insert / delete
    Inserting or deleting an item in the middle of an array requires every item after it to be re-indexed
  • Slow searches
    To find an item in the array, we must iterate through the list which requires O(n) time
  • Indexes are not flexible
    An index only points to a location in the array but provides no other meaning about the item

Arrays in JavaScript:

const jobOfferList = [
  'Facebook',
  'Amazon',
  'Apple',
  'Netflix',
  'Google',
  'Skilled.dev',
  'gitconnected',
];

Arrays in Interviews:

  • Be able to iterate over and find items in an array
  • Know how to handle an array of objects or other data structures
  • Iterate a matrix (2-dimensional arrays and higher)
  • An array may or may not be sorted - you should typically ask if the prompt does not state
  • Assume sorting an array is O(n log n) when using native sort functions
  • Know the implications of having sorted vs unsorted data
  • Know how to group/create subarrays from an input array
  • Compare multiple arrays based on values, lengths, etc.
  • Utilize an array for fast lookups like a hash table when the keys can be integers
  • Assume arrays are dynamic for higher-level or scripted languages (ie. JavaScript, Python)
  • Typically assume dynamic arrays for compiled languages unless a fixed size is given or memory management is important

Arrays Explained

Arrays store items sequentially in memory where items are any data type. When we create an array, our programming language finds contiguous memory slots, and the index of the array points directly to the location in memory. This direct mapping of an index to a memory location is how we get O(1) lookups.

const arr = ['h', 'e', 'l', 'l', 'o'];

// Underneath the hood...

Index               0     1     2     3     4
                    |     |     |     |     |
Memory address     418   419   420   421   422
                   ___   ___   ___   ___   ___
Items              "h"   "e"   "l"   "l"   "o"

What actually happens is that our programming language remembers the first item's memory address, or the "datum". Then if we look up arr[3], our programming language knows to immediately return the item 3 spots after our datum.

When we push or pop items from the end of the array, these are also constant time O(1) operations.

Our array performs poorly when we want to search for a particular item. For example, if we want to find "l" in our array above, we would have a worst-case of needing to look through all n items. However, if the data is sorted, we can use a binary search which is much faster at O(log n).

By nesting arrays you can represent a matrix. For interviews, you should be comfortable iterating a matrix and also know how to swap items.

3x3 matrix

const matrix = [      //             columns
  ['a', 'b', 'c'],    //  r    "a"  |  "b"  |  "c"
  ['z', 'y', 'x'],    //  o  -----------------------
  ['i', 'j', 'k'],    //  w    "z"  |  "y"  |  "x"
];                    //  s  -----------------------
                      //       "i"  |  "j"  |  "k"


// array[rowIndex][columnIndex]
array[0][0] // "a"
array[1][2] // "x"

Array Inserts are O(n)

One of the things we love about arrays is that we get a list of items that are sequentially numbered with an index.

This comes with a tradeoff though. If we want to insert an item in the middle of the array, we would have to shift and re-index each item after it in the array. So if we inserted an item at the beginning, we would have to re-index all n items. That means, the previous array[0] item would have to be moved to the array[1] slot in memory the previous array[1] item would have to be moved to the array[2] item slot in memory, and so on for each element. Given this worst-case, we can say inserting an array requires O(n) time. Even if it's in the middle of the array it would be O(0.5 n) which if we drop the constant is still O(n).

// Initial array
  0    1    2    3
['w', 'o', 'l', 'd'];
          ^
          |
         "r"

// We want to insert "r" at index 2 but there is already an item here,
// We have to shift all the items that come after that spot and update their indexes
               (2+1)(3+1)
  0    1    2    3    4
['w', 'o', 'r', 'l', 'd'];
                ->   ->

Array Deletes are O(n)

Deletes are very similar to inserts. The difference is that if we remove an item, all the ones that come after it must be shifted inward by one spot. By the same logic, this also results in an O(n) operation.

// Initial array
  0    1    2    3    4
['l', 'e', 'a', 'r', 'n'];

// We want to delete "l" which is at index 0
// Shift all the items after the deleted one inward and update their indexes
(1-1)(2-1)(3-1)(4-1)
  0    1    2    3
['e', 'a', 'r', 'n'];
  <-   <-   <-   <-

Dynamic Arrays vs Static Arrays

Dynamic arrays have become the most utilized array implementation in interview questions. In fact, in many high-level or scripted programming languages like JavaScript and Python, this is the only implementation of arrays.

However, it's worth learning about another implementation which is static arrays. A static array is a fixed size which must be set when you declare the array. For example, in Java you can declare a static array as follows:

int[] intArray = new int[20];

This array can only hold 20 items, and these items can only be of type integer. This means that when we create the array, our programming language finds 20 free memory slots and allocates them to our static array.

Technicaly it will find 160 (8 x n) memory slots because each integer requires 8 bytes of storage for a 64-bit operating systems.

Static arrays require some additional thought up front to decide the size and type, and they may even seem more complicated if you come from a language like JavaScript or Python. Beyond that though, nothing really happens - we just declare the size and type of data it holds, and then the memory is allocated to us accordingly.

Dynamic arrays are easier to use as developers but are more complicated underneath the hood because it must handle the array's ability to change size and (in some languages) hold arbitrary types of data. The fundamentals of the array are the same - it allocates contiguous blocks of memory. This means the size of your array is likely smaller than what has been allocated. While pushing items to the array, if you reach the maximum size, the programming language will then create a new array that is double the size and copy all the items over.

Doubling is a common way to handle it, but it is up to the programming language or operating system on how to handle the new memory allocation.

So if we had a full dynamic array with 2 items and tried to push another item onto it, underneath the hood our programming language would create a new array of size 4, copy the items over, and add the new element to the end. Once we reached 4, it would double again to 8, and so on.

227271271327138SizeCapacity271384

For dynamic arrays, we must consider the size vs. capacity. The size is the number of items in the array, or what we get if find its length. The capacity is the total number of memory slots allocated to the array. So capacity >= size, and the array will double its capacity if we try to push an additional item beyond the limit.

We have stated that pushing items is O(1), which is true when the capacity of our array is larger than the size. However, when we double the size, a dynamic array copies the elements to a new location in memory with the additional space, and this costs O(n) time. We have many more constant time pushes vs. one O(n) when we reach the array limit. As our number of items n grows, the number of constant O(1) continues to grow but we still only have one O(n) as size reaches the maximum capacity, and eventually the constant time operations overpower the single linear time push, so we call it O(1). This is an example of .

In summary: static arrays are fixed size and are set by the developer when the array is declared. Dynamic arrays grow in size which is managed underneath the hood by the programming language.

Prev
Valid Sudoku Board
Next
Implement an Array
Loading...

Table of Contents