Arrays Introduction

Array vs Object

• Arrays for storing ordered collections.
• Objects for storing keyed collections.

Array - Big O Complexity

Operation | Big O
lookup | O(1)
push | O(1)
insert | O(n)
delete | O(n)

Code

• If you don't need to loop through all the items, it is O(1).
• Otherwise, if you need to loop through all the items in order to change indices or to put or remove things, it is O(n).

// 4 * 4 = 16 bytes of storage
const strings = ['a', 'b', 'c', 'd'];
strings[2]

const numbers = [1, 2, 3, 4, 5];

//push
strings.push('e');  // O(1)

//pop
strings.pop();  // O(1)
strings.pop();  // O(1)

//unshift
// 'x' will push all elements to their right
// ['x', 'a', 'b', 'c', 'd'];
//   0    1    2    3    4
strings.unshift('x')  // O(n)

//splice
strings.splice(2, 0, 'alien');  // O(n)

Static vs Dynamic Arrays

• JavaScript Array is dynamic

Big O Complexity of Dynamic Array

Array | Operation | Big O | Dynamic Array | Big O
lookup | O(1) | lookup | O(1)
push | O(1) | append* | O(1) or O(n)
insert | O(n) | insert | O(n)
delete | O(n) | delete | O(n)

Side Study : Classes in JS

class Hero {
  constructor(name, level) {
    this.name = name;
    this.level = level;
  }
  greet = () => {
    return `${this.name} says hello.`;
  }
}

class Mage extends Hero {
  constructor(name, level, spell) {
    super(name, level);
    this.spell = spell;
  }
  greet() {
    super.greet()
  }
}

const hero1 = new Hero('Varg', 1);
const hero2 = new Mage('Lejon', 2, 'Magic Missile');
hero2.greet()

Implementing An Array

class MyArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }
  get(index) {
    return this.data[index];  // O(1)
  }

  push(item) {  
    this.data[this.length] = item;  // O(1)
    this.length++;
    return this.data;
  }
  
  pop() {
    const lastItem = this.data[this.length - 1];  // O(1)
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }
  
  deleteAtIndex(index) {
    const item = this.data[index];
    this.shiftItems(index); // O(n)
    return item;
  }
  
  shiftItems(index) {
    for (let i = index; i < this.length - 1; i++) { 
      this.data[i] = this.data[i + 1];  // O(n)
    }
    delete this.data[this.length - 1];
    this.length--;
  }
}

const myArray = new MyArray();
myArray.push('hi');
myArray.push('you');
myArray.push('!');
myArray.get(0);
myArray.pop();
myArray.deleteAtIndex(0);
myArray.push('are');
myArray.push('nice');
myArray.shiftItems(0);

Exercise

Reverse a String

const reverse1 = (str = '') => {
  if(!str || typeof str != 'string' || str.length < 2 ) return str;
  
  const backwards = [];
  const totalItems = str.length - 1;
  for(let i = totalItems; i >= 0; i--){
    backwards.push(str[i]);
  }
  return backwards.join('');
}

const reverse2 = (str = '') => str.split('').reverse().join('');
const reverse3 = (str = '') => [...str].reverse().join('');

//function reverse2(str) {
//	return str.split('').reverse().join('');
//}
//const reverse3 = str => str.split('').reverse().join('');

reverse1('Timbits Hi')
reverse2('Timbits Hi')
reverse3('Timbits Hi')

Merge Sorted Arrays

Version 1 : not the cleanest

function mergeSortedArrays(array1, array2) {
  const mergedArray = [];

  let array1Item = array1[0];
  let array2Item = array2[0];
  let i = 1;
  let j = 1;

  // check input
  if (array1.length === 0) return array2;
  if (array2.length === 0) return array1;

  while (array1Item || array2Item) {
    if (!array2Item || array1Item < array2Item) {
      mergedArray.push(array1Item);
      array1Item = array1[i];
      i++;
    } else {
      mergedArray.push(array2Item);
      array2Item = array2[j];
      j++;
    }
  }

  return mergedArray;
}

mergeSortedArrays([0, 3, 4, 31], [4, 6, 30]);

Version 2 : cleaner

const ascendingSort = (a, b) => a - b;
const descendingSort = (a, b) => b - a;

const mergeSortedArrays = (arr1, arr2) => arr1.concat(arr2).sort(ascendingSort);
mergeSortedArrays([0,3,4,31], [3,4,6,30]);

Two Sum

// Given an array of integers, return indices of the two numbers such that they add up to a specific target.
// You may assume that each input would have exactly one solution, and you may not use the same element twice.

// Given nums = [2, 7, 11, 15], target = 9,
// Because nums[0] + nums[1] = 2 + 7 = 9,
// return [0, 1].

const twoSum = (nums, target) => {
  let low = 0;
  let high = nums.length - 1;
  while(low < high) {
    if(nums[low] + nums[high] === target) return [low, high];
    else if(nums[low] + nums[high] > target) high--;
    else low++;
  }
};

twoSum([2, 3, 4, 5, 6], 10)