array.asc

Array

Arrays are one of the most used data structures. You probably have used it a lot but are you aware of the runtimes of splice, shift, indexOf and other operations? In this chapter, we are going deeper into the most common operations and their runtimes.

Array Basics

An array is a collection of things (strings, characters, numbers, objects, etc.). They can be many or zero.

Tip	Strings are a collection of Unicode characters and most of the array concepts apply to them.

Fixed vs. Dynamic Size Arrays

Some programming languages have fixed size arrays like Java and C++. Fixed size arrays might be a hassle when your collection gets full, and you have to create a new one with a bigger size. For that, those programming languages also have built-in dynamic arrays: we have vector in C++ and ArrayList in Java. Dynamic programming languages like JavaScript, Ruby, and Python use dynamic arrays by default.

Arrays look like this:

Figure 1. Array representation: each value is accessed through an index.

Arrays are a sequential collection of elements that can be accessed randomly using an index. Let’s take a look into the different operations that we can do with arrays.

Insertion

Arrays are built-in into most languages. Inserting an element is simple; you can either add them at creation time or after initialization. Below you can find an example for both cases:

Inserting elements into an array

// (1) Add elements at the creation time:
const array = [2, 5, 1, 9, 6, 7];

// (2) initialize an empty array and add values later
const array2 = [];
array2[3] = 1;
array2[100] = 2;
array2 // [empty × 3, 1, empty × 96, 2]

Using the index, you can replace whatever value you want. Also, you don’t have to add items next to each other. The size of the array will dynamically expand to accommodate the data. You can reference values at whatever index you like: index 3 or even 100! In array2, we inserted 2 numbers but the length is 101 and there are 99 empty spaces.

console.log(array2.length); // 101
console.log(array2); // [empty × 3, 1, empty × 96, 2]

The runtime for inserting elements using index is always is constant: O(1).

Inserting at the beginning of the array

What if you want to insert a new element at the beginning of the array? You would have to push every item to the right.

Insert to head

const array = [2, 5, 1, 9, 6, 7];
array.unshift(0); // ↪️ 8
// array: [0, 2, 5, 1, 9, 6, 7]

As you can see, 2 was at index 0, now was pushed to index 1, and everything else is on a different index. unshift takes O(n) since it affects all the elements in the array.

JavaScript built-in array.unshift

The unshift() method adds one or more elements to the beginning of an array and returns the new length of the array.

Runtime: O(n).

Inserting at the middle of the array

Inserting a new element in the middle involves moving part of the array but not all of the items.

Inserting element in the middle

const array = [2, 5, 1, 9, 6, 7];
array.splice(1, 0, 111); // ↪️ [] (1)
// array: [2, 111, 5, 1, 9, 6, 7]

1. at position 1, delete 0 elements and insert 111.

The Big O for this operation would be O(n) since in worst case it would move most of the elements to the right.

JavaScript built-in array.splice

The splice() method changes the contents of an array by removing existing elements or adding new elements. Splice returns an array containing the deleted elements.

Runtime: O(n).

Inserting at the end of the array

We can push new values to the end of the array like this:

Insert to tail

const array = [2, 5, 1, 9, 6, 7];
array.push(4); // ↪️ 7 (1)
// array: [2, 5, 1, 9, 6, 7, 4]

1. The 4 element would be pushed to the end of the array. Notice that push returns the new length of the array.

Adding to the tail of the array doesn’t change other indexes. E.g., element 2 is still at index 0. So, this is a constant time operation O(1).

JavaScript built-in array.push

The push() method adds one or more elements to the end of an array and returns the new length of the array.

Runtime: O(1).

Searching by value and index

Searching by index is very easy using the [] operator:

Search by index

const array = [2, 5, 1, 9, 6, 7];
array[4]; // ↪️ 6

Searching by index takes constant time - O(1) - to retrieve values out of the array. If we want to get fancier, we can create a function:

Search by index

/**
 * Search for array's element by index
 *
 * @example Given array = [2, 5, 1, 9, 6, 7, -1];
 *    searchByIndex(array, 3); //↪️ 9
 *    searchByIndex(array, 6); //↪️ -1
 *    searchByIndex(array, 13); //↪️ undefined
 * @param {array} array
 * @param {number} index
 * @returns {any} value or undefined if not found
 */
function searchByIndex(array, index) {
  return array[index];
}

Finding out if a value is in the array or not is a different story.

Search by value

/**
 * Search for array's element by value
 *
 * @example Given array = [2, 5, 1, 9, 6, 7];
 *    searchByValue(array, 9); //↪️ 3
 *    searchByValue(array, 13); //↪️ -1
 * @param {array} array
 * @param {any} value
 */
function searchByValue(array, value) {
  for (let index = 0; index < array.length; index++) {
    const element = array[index];
    if (element === value) return index;
  }
  return -1;
}

We would have to loop through the whole array (worst case) or until we find it: O(n).

Deletion

There are three possible scenarios for deletion (similar to insertion): removing at the beginning, middle or end.

Deleting element from the beginning

Deleting from the beginning can be done using the splice function and also the shift. For simplicity, we will use the latter.

Deleting from the beginning of the array.

const array = [2, 111, 5, 1, 9, 6, 7];
// Deleting from the beginning of the array.
array.shift(); // ↪️2
array.shift(); // ↪️111
// array: [5, 1, 9, 6, 7]

As expected, this will change every index, so this takes O(n).

JavaScript built-in array.shift

The shift() method shift all elements to the left. In turn, it removes the first element from an array and returns that removed element. This method changes the length of the array.

Runtime: O(n).

Deleting element from the middle

We can use the splice method for deleting an item from the middle of an array.

Deleting from the middle

const array = [0, 1, 2, 3, 4];
// Deleting from the middle
array.splice(2, 1); // ↪️[2] (1)
// array: [0, 1, 3, 4]

1. delete 1 element at position 2

Deleting from the middle might cause most of the elements of the array to move up one position to fill in for the eliminated item. Thus, runtime: O(n).

Deleting element from the end

Removing the last element is very straightforward:

Deleting last element from the array

const array = [2, 5, 1, 9, 111];
array.pop();  // ↪️111
// array: [2, 5, 1, 9]

No other element has been shifted, so it’s an O(1) runtime.

JavaScript built-in array.pop

The pop() method removes the last element from an array and returns that element. This method changes the length of the array.

Runtime: O(1).

Array Complexity

To sum up, the time complexity of an array is:

Table 1. Time/Space complexity for the array operations

Data Structure	Searching By		Inserting at the			Deleting from			Space
	Index/Key	Value	beginning	middle	end	beginning	middle	end
Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(1)	O(n)

Table 2. Array Operations time complexity

Operation	Time Complexity	Usage
push	O(1)	Insert element to the right side.
pop	O(1)	Remove the rightmost element.
unshift	O(n)	Insert element to the left side.
shift	O(n)	Remove leftmost element.
splice	O(n)	Insert and remove from anywhere.

Interview Questions

Max Subarray

Given an array of integers, find the maximum sum of consecutive elements (subarray).

link:../../interview-questions/max-subarray.js[role=include]
  // write you code here
}

Solution: [array-q-max-subarray]

Best Time to Buy and Sell an Stock

You are given an array of integers. Each value represents the closing value of the stock on that day. You are only given one chance to buy and then sell. What’s the maximun profit you can obtain? (Note: you have to buy first and then sell)

link:../../interview-questions/buy-sell-stock.js[role=include]
  // write you code here
}

Solution: [array-q-buy-sell-stock]