Skip to content

Latest commit

 

History

History
563 lines (421 loc) · 17.1 KB

File metadata and controls

563 lines (421 loc) · 17.1 KB

Array

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.

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 characters. Most of the array methods apply to strings as well.

Arrays look like this:

image
Figure 1. Array representation: You can access each value in constant time through its index.
Read and Update

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.

Reading elements from an array and string
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!

Reading elements from an array and string
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.
Insertion

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.

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. We can use the following method:

Syntax
const newArrLength = arr.unshift(element1[, ...[, elementN]]);

Here’s an example:

Insert to head
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.

JavaScript built-in 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 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. We can use splice for that:

Syntax
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.

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 the worst case, it would move most of the elements to the right.

JavaScript built-in 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).

Inserting at the end of the array

For inserting items at the end of the array, we can use: push.

Syntax
const newArrLength = arr.push([element1[, ...[, elementN]]]);

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 its new length.

Runtime: O(1).

Searching by value and index

As we saw before, searching by the 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.

Searching by value can be done using indexOf.

Syntax
const index = arr.indexOf(searchElement[, fromIndex]);

If the value is there, we will get the index, otherwise -1.

Search by value
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).

Deletion

There are three possible deletion scenarios (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 the shift. For simplicity, we will use the latter.

Syntax
const removedElement = arr.shift();
let arrDeletedItems = arr.splice(start[, deleteCount[, item1[, item2[, ...]]]]);
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
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).

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.

You can delete multiple items at once:

Deleting from the middle
const array = [0, 1, 2, 3, 4];
// Deleting from the middle
array.splice(2, 3); // ↪️ [ 2, 3, 4 ] (1)
console.log(array); // [0, 1]
  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).

Deleting element from the end

Removing the last element is very straightforward using pop:

Syntax
const removedItem = arr.pop();

Here’s an example:

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

While deleting the last element, no other item was touched, so that’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 on the right side.

pop

O(1)

Remove the rightmost element.

[]

O(1)

Search for element by index.

indexOf

O(n)

Search for element by value.

unshift

O(n)

Insert element on the left side.

shift

O(n)

Remove leftmost element.

splice

O(n)

Insert and remove from anywhere.

slice

O(n)

Returns a shallow copy of the array.

Array Patterns for Solving Interview Questions

Many programming problems involve manipulating arrays. Here are some patterns that can help you improve your problem-solving skills.

Two Pointers Pattern

Usually, we use one pointer to navigate each element in an array. However, there are times when having two pointers (left/right, low/high) comes in handy. Let’s do some examples.

AR-A) Given a sorted array of integers, find two numbers that add up to a target and return their values.

Function Signature
/**
 * Find two numbers that add up target.
 * @param arr - The array of integers
 * @param target - The target
 * @returns {number[]} - array with the values that add up to target.
 */
function twoSum(arr, target) {
  // give it a try on your own ...
}
Examples
twoSum([ -5, -3, 1, 10 ], 7); // [-3, 10] // (10 - 3 = 7)
twoSum([ -5, -3, -1, 1, 2 ], 30); // [] // no 2 numbers add up to 30
twoSum([ -3, -2, -1, 1, 1,  3,  4], -4); // [-3, -1] // (-3 -1 = -4)

Solutions:

One naive solution would be to use two pointers in a nested loop:

Solution 1: Brute force
function twoSum(arr, target) {
  for (let i = 0; i < arr.length - 1; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] + arr[j] === target) return [arr[i], arr[j]];
  return [];
}

The runtime of this solution would be O(n^2). Because of the nested loops. Can we do better? We are not using the fact that the array is SORTED!

We can use two pointers: one pointer starting from the left side and the other from the right side.

Depending on whether the sum is bigger or smaller than the target, we move right or left. If the sum is equal to the target, we return the current left and right pointer’s values.

Solution 2: Two Pointers
function twoSum(arr, target) {
  let left = 0, right = arr.length -1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [arr[left], arr[right]];
    else if (sum > target) right--;
    else left++;
  }
  return [];
}

These two pointers have a runtime of O(n).

Warning
This technique only works for sorted arrays. If the array was not sorted, you would have to sort it first or choose another approach.
Sliding Window Pattern

The sliding window pattern is similar to the two pointers. The difference is that the distance between the left and right pointer is always the same. Also, the numbers don’t need to be sorted. Let’s do an example!

AR-B) Find the max sum of an array of integers, only taking k items from the right and left side sequentially. Constraints: k won’t exceed the number of elements in the array: 1 ⇐ k ⇐ n.

Function Signature
/**
 * Find the max sum of an array of integers,
 * only taking `k` items from the right and left side.
 *
 * @param {number[]} arr - The array of integers
 * @param {number} k - The number of elements to sum up.
 * @returns {number}
 */
function maxSum(arr, k) {
  // Give it a try
};
Examples
maxSum([1,2,3], 3); // 6 // (1 + 2 + 3 = 6)
maxSum([1,1,1,1,200,1], 3); // 202 // (1 + 200 + 1 = 202)
maxSum([3, 10, 12, 4, 7, 2, 100, 1], 3); // 104 // (3 + 1 + 100 = 104)
maxSum([1,200,1], 1); // 6 // (1 + 2 + 3 = 6)

There are multiple ways to solve this problem. Before applying the sliding window, let’s consider this other algorithm:

Backtracking algorithm

Let’s take [3, 10, 12, 4, 7, 2, 100, 1], k = 3 as an example.

  • We have two initial choices: going left with 3 or right with 1.

  • We can take the first element from the left side 3; from there, we can keep going left with 10 or right 1.

  • If we go right with 1 on the right side, next, we have two options from the right side 100 or 10.

  • If we go with 100, then we compute the sum 3 + 1 + 100 = 104.

  • Repeat with other combinations and keep track of the max sum.

How many combinations can we form? 2^k, since in the worst-case k is equal to n, then we have a runtime of O(2^n)!

We can also visualize all the options as follows. If you add up the numbers from top to bottom, you get the result for all combinations:

graph G {
    0 -- 3
    0 -- 1

    3 -- 10
    3 -- a1

    10 -- 12
    10 -- b1

    a1 -- a10
    a1 -- 100

    1 -- a3
    1 -- a100

    a3 -- b10
    a3 -- b100

    a100 -- b3
    a100 -- 2

    1, a1, b1 [label = 1 color = red]
    10, a10, b10 [label = 10 color = red]
    3, a3, b3 [label = 3 color = red]
    100, a100, b100 [label = 100 color = red]

    12 -- res1 [color = gray]
    b1 -- res2 [color = gray]
    a10 -- res3 [color = gray]
    100 -- res4 [color = gray]
    b10 -- res5 [color = gray]
    b100 -- res6 [color = gray]
    b3 -- res7 [color = gray]
    2 -- res8 [color = gray]

    res1 [label = "Sum: 25", shape=plaintext, fontcolor=gray]
    res2 [label = "Sum: 14", shape=plaintext, fontcolor=gray]
    res3 [label = "Sum: 14", shape=plaintext, fontcolor=gray]
    res4 [label = "Sum: 104", shape=plaintext, fontcolor=gray]
    res5 [label = "Sum: 14", shape=plaintext, fontcolor=gray]
    res6 [label = "Sum: 104", shape=plaintext, fontcolor=gray]
    res7 [label = "Sum: 104", shape=plaintext, fontcolor=gray]
    res8 [label = "Sum: 103", shape=plaintext, fontcolor=gray]
}

Notice that many middle branches (in red color) have the same numbers, but in a different order, so their sums oscillate between 104 and 14. That’s why this algorithm is not very optimal for this problem.

Sliding window algorithm

Another approach is using sliding windows. Since the sum always has k elements, we can compute the cumulative sum for the k first elements from the left. Then, we slide the "window" to the right and remove one from the left until we cover all the right items. In the end, we would have all the possible combinations without duplicated work.

Check out the following illustration:

sliding window for arrays

Here’s the implementation:

Solution: using sliding window pointers
function maxSum(arr, k) {
  let left = k - 1;
  let right = arr.length -1;
  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i];
  let max = sum;

  for (let i = 0; i < k; i++) {
    sum += arr[right--] - arr[left--];
    max = Math.max(max, sum);
  }

  return max;
};

The difference between the two pointers pattern and the sliding windows, it’s that we move both pointers at the same time to keep the length of the window the same.

The runtime for this code is: k. As we move the window k times. Since k ⇐ n, the final runtime is O(n).

Practice Questions

Max Subarray

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])

Common in interviews at: FAANG, Microsoft

link:../../interview-questions/max-subarray.js[role=include]
  // write you code here
}
Best Time to Buy and Sell a Stock

AR-2) You have 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)

Common in interviews at: Amazon, Facebook, Bloomberg

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