Arrays are one of the most used data structures. You probably have used it a lot already. But, are you aware of the runtimes of push
, splice
, shift
, indexOf
, and other operations? In this chapter, we are going deeper into the most common operations and their runtimes.
An array is a collection of things (strings, characters, numbers, objects, etc.). They can be many or zero.
Tip
|
Strings are a collection of characters. Most of the array methods apply to strings as well. |
Arrays look like this:
Arrays are a contiguous collection of elements that can be accessed randomly using an index. This access by index operation takes O(1)
time. Let’s take a look at the different functions that we can do with arrays.
const array = [2, 5, 1, 9, 6, 7];
const string = "hello";
console.log(array[2]); // 1
console.log(string[1]); // "e"
As you can see, you can access the string’s characters using the same operator as arrays.
You can update arrays in the same way, using the []
operator. However, you can’t modify strings. They are immutable!
const array = [2, 5, 1, 9, 6, 7];
const string = "hello";
array[2] = 117;
console.log(array[2]); // 117
string[1] = "z"; // doesn't change the string.
console.log(string[1]); // "e"
Warning
|
When you try to modify and string, you won’t get an error or anything. It just gets ignored! Your only option is to create a new string with the adjusted value. |
Insertions on an array have different times complexities. O(1): constant time (on average) to append a value at the end of the array. O(n): linear time to insert a value at the beginning or middle.
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. We can use the following method:
const newArrLength = arr.unshift(element1[, ...[, elementN]]);
Here’s an example:
const array = [2, 5, 1];
array.unshift(0); // ↪️ 8
console.log(array); // [ 0, 2, 5, 1 ]
array.unshift(-2, -1); // ↪️ 6
console.log(array); // [ -2, -1, 0, 2, 5, 1 ]
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 of the array.
array.unshift
The unshift()
method adds one or more elements to the beginning of an array and returns its new length.
Runtime: O(n)
.
Inserting a new element in the middle involves moving part of the array but not all of the items. We can use splice
for that:
const arrDeletedItems = arr.splice(start[, deleteCount[, item1[, item2[, ...]]]]);
Based on the parameters it takes, you can see that we can add and delete items. Here’s an example of inserting 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]
-
at position
1
, delete0
elements and insert111
.
The Big O for this operation would be O(n) since, in the worst case, it would move most of the elements to the right.
array.splice
The splice()
method changes an array’s contents by removing existing elements or adding new items. Splice returns an array containing the deleted items.
Runtime: O(n).
For inserting items at the end of the array, we can use: push.
const newArrLength = arr.push([element1[, ...[, elementN]]]);
We can push new values to the end of the array like this:
const array = [2, 5, 1, 9, 6, 7];
array.push(4); // ↪️ 7 (1)
// array: [2, 5, 1, 9, 6, 7, 4]
-
The
4
element would be pushed to the end of the array. Notice thatpush
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).
array.push
The push()
method adds one or more elements to the end of an array and returns its new length.
Runtime: O(1).
As we saw before, searching by the index is very easy using the []
operator:
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.
Searching by value can be done using indexOf
.
const index = arr.indexOf(searchElement[, fromIndex]);
If the value is there, we will get the index, otherwise -1
.
const array = [2, 5, 1, 9, 6, 7];
console.log(array.indexOf(9)); // ↪️ 3
console.log(array.indexOf(90)); // ↪️ -1
Internally, indexOf
has to loop through the whole array (worst case) or until we find the first occurrence. Time complexity is O(n).
There are three possible deletion scenarios (similar to insertion): removing at the beginning, middle, or end.
Deleting from the beginning can be done using the splice
function and the shift
. For simplicity, we will use the latter.
const removedElement = arr.shift();
let arrDeletedItems = arr.splice(start[, deleteCount[, item1[, item2[, ...]]]]);
const array = [2, 111, 5, 1, 9, 6, 7];
// Deleting from the beginning of the array.
array.shift(); // ↪️ 2
array.shift(); // ↪️ 111
console.log(array); // [5, 1, 9, 6, 7]
array.splice(0, 1); // ↪️ [ 5 ]
console.log(array); // [ 1, 9, 6, 7 ]
As expected, this will change every index on the array, so this takes linear time: O(n).
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).
We can use the splice
method for deleting an item from the middle of an array.
You can delete multiple items at once:
const array = [0, 1, 2, 3, 4];
// Deleting from the middle
array.splice(2, 3); // ↪️ [ 2, 3, 4 ] (1)
console.log(array); // [0, 1]
-
delete 3 elements starting on position 2
Deleting from the middle might cause most of the array elements to move up one position to fill in for the eliminated item. Thus, runtime: O(n).
Removing the last element is very straightforward using pop:
const removedItem = arr.pop();
Here’s an example:
const array = [2, 5, 1, 9, 111];
array.pop(); // ↪️111
// array: [2, 5, 1, 9]
No other element was touched, so it’s an O(1) runtime.
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).
To sum up, the time complexity of an array is:
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) |
Operation |
Time Complexity |
Usage |
|
O(1) |
Insert element on the right side. |
|
O(1) |
Remove the rightmost element. |
|
O(1) |
Search for element by index. |
|
O(n) |
Search for element by value. |
|
O(n) |
Insert element on the left side. |
|
O(n) |
Remove leftmost element. |
|
O(n) |
Insert and remove from anywhere. |
|
O(n) |
Returns shallow copy of the array. |
AR-1) Given an array of integers, find the maximum sum of consecutive elements (subarray).
Examples:
maxSubArray([1, -3, 10, -5]); // 10 (taking only 10)
maxSubArray([-3, 4,-1, 2, 1, -5]); // 6 (sum [4,-1, 2, 1])
maxSubArray([-2, 1, -3, 4, -1, 3, 1]); // 7 (sum [4,-1, 3, 1])
link:../../interview-questions/max-subarray.js[role=include]
// write you code here
}
Solution: [array-q-max-subarray]
AR-2) You are given an array of integers. Each value represents the closing value of the stock on that day. You have only one chance to buy and then sell. What’s the maximum profit you can obtain? (Note: you have to buy first and then sell)
Examples:
maxProfit([1, 2, 3]) // 2 (buying at 1 and selling at 3)
maxProfit([3, 2, 1]) // 2 (no buys)
maxProfit([5, 10, 5, 10]) // 5 (buying at 5 and selling at 10)
link:../../interview-questions/buy-sell-stock.js[role=include]
// write you code here
}
Solution: [array-q-buy-sell-stock]