Interview Question

Implement an Array

We will implement an array using an object, and it will have the methods get, push, pop, insert, and remove. We will also need to track the length of the array. Calling get, push, pop, and length should all take O(1) time, and insert/remove will take O(n) time.

The reason insert and remove require O(n) time is that we need to shift the items to re-index them to their new spot in the array.

Visually, what we're creating is:

class DynamicArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }

  get(index) {
    // get an item at an index
  }
  push(item) {
    // add an item to the end of the array
  }
  pop() {
    // remove the last item in the array
  }
  insert(index, item) {
    // add an item at any index
  }
  remove(index) {
    // remove an item at any index
  }
}

In the constructor, we initialize our length to 0 and the array's data to an empty hash table.

get(index)

This will be the most simple method in our object. Since we are storing the array in a hash table with the index as the key, we will just return the value set for that index.

get(index) {
  return this.data[index];
}

push(item)

When we push an item to our array, we want to add this item after the last index. Since arrays are 0-based indexing, the current length will also be the new index which we are pushing onto. After adding the item, we need to increment our new length, and the function will return the new length of the array.

push(item) {
  this.data[this.length] = item;
  this.length++;

  return this.length;
}

pop()

The pop method removes the last item from the array and returns it from the method. The last item will correspond to length - 1, so we will delete at that index, decrement our length, and then return the item.

pop() {
  const poppedItem = this.data[this.length - 1];
  delete this.data[this.length - 1];
  this.length--;

  return poppedItem;
}

insert(index, item)

When we insert an item at an index, we change the index for all the items that come after it. This requires using a loop to update the index for each item individually which takes linear O(n) time.

Notice that we start at the end of the array since this is where the empty spot is with the length increase. We increment inward until we have shifted all items from the end to the index. Now the new item can be added at that index.

insert(index, item) {
  // Create our new length
  this.length++;

  // Shift items up one spot from the insertion index to the new final spot in the array.
  // We iterate from the back since this is our new empty item
  for (let i = this.length - 1; i > index; i--) {
    this.data[i] = this.data[i - 1];
  }

  // Add the new item
  this.data[index] = item;

  // Return the array
  return this.data;
}

remove(index)

When we delete an item at an index, we again change the index for all the items that come after it. This requires using a loop to update the index for each item individually which takes linear O(n) time.

This time we start at the item we're removing and replace the current value with the one that comes after. Once we reach the end of the array, we delete the last item since our length has shrunk by 1 and that item was moved inward.

remove(index) {
  const itemToBeRemoved = this.data[index];

  // Shift items inward one index towards the one we remove
  for (let i = index; i < this.length - 1; i++) {
    this.data[i] = this.data[i + 1];
  }

  // The item we want to delete is just overwritten to the value of the index that comes after it.

  // Since all items were shifted inward one spot, we need to remove the last index/item since our array size shrinks by 1
  delete this.data[this.length - 1];
  this.length--;

  return itemToBeRemoved;
}

Complete Array Implementation

You can use the implementation in a REPL or see the completed code below:

class DynamicArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }

  get(index) {
    return this.data[index];
  }

  push(item) {
    this.data[this.length] = item;
    this.length++;

    return this.length;
  }

  pop() {
    const poppedItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;

    return poppedItem;
  }

  insert(index, item) {
    this.length++;

    for (let i = this.length - 1; i > index; i--) {
      this.data[i] = this.data[i - 1];
    }

    this.data[index] = item;

    return this.data;
  }

  remove(index) {
    const itemToBeRemoved = this.data[index];

    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }

    delete this.data[this.length - 1];
    this.length--;

    return itemToBeRemoved;
  }
}

Table of Contents