Intro

• Arrays, sometimes called lists, organizes items sequentially, i.e. one after another in memory.
• Arrays are the simplest (an most wildly used) data structures because they have the least amount of rules and they’re stored in continuous memory. They also have the smallest of footprint of any data structure.
• The big-O of different methods of arrays are:
  • Lookup: $\text{O(1)}$
  • Push/Pop: $\text{O(1)}$
  • Append: $\text{O(1)}$ $\rightarrow$ in static arrays and $\text{O(n)}$ $\rightarrow$ in dynamic arrays.
  • Insert: $\text{O(n)}$ $\rightarrow$ because of all the re-indexing
  • delete: $\text{O(n)}$ $\rightarrow$ because of all the re-indexing

const strings= ['a', 'b', 'c', 'd'];
const numbers = [1,2,3,4,5];
// Variable array is somewhere in memory and the computer knows it.
// When I do array[2], i'm telling the computer, hey go to the array and grab the 3rd item from where the array is stored.


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

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

//unshift
strings.unshift('x') // O(n)

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

console.log(strings)

Note: In the example above, if we’re on a 32-bit systems, an array of size 4 would

There are two types of arrays:

1. Static: They’re fixed in size, i.e. the array size should be declared ahead of time.
2. Dynamic: Dynamic arrays allow us to copy and rebuild an array at a new location with more memory if needed.
   • Note: In languages such as Javascript or Python, the arrays are dynamic by default. But in C++, for instance, the array size need to be defined ahead of time: int a[20]; or int b[5] {1,2,3,4,5};. If we want add another element, we have to redefine them (allocate a new space in memory).

Implementing an Array

We use JS class to create an array. It will be similar in other languages.

class MyArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }
  get(index) {
    return this.data[index];
  }
  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.data;
  }
  pop() {
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }
  deleteAtIndex(index) {
    const item = this.data[index];
    this.shiftItems(index);
    return item;
  }
  shiftItems(index) {
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    console.log(this.data[this.length - 1]);
    delete this.data[this.length - 1];
    this.length--;
  }
}

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

Note: In interviews, remember to turn any string questions into arrays, because strings are simply an array of characters.

---

Exercise: create a function that reverses a string. For example: My name is Ali $\rightarrow$ ilA si eman yM

function reverse(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('');
}

function reverse2(str){
  //check for valid input
  return str.split('').reverse().join('');
}

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

Python solution

def reverse(string):
    x = list(string)
    y = [x[len(x)-i-1] for i in range(len(x))]
    return ''.join(y)

print(reverse('My name is Ali'))

---

Exercise: Given two sorted arrays, can you merge them into one sorted array? Example: [0,3,4,31] & [4,6,30] $\rightarrow$ [0,3,4,4,6,30,31]

function mergeSortedArrays(array1, array2){
  const mergedArray = [];
  let array1Item = array1[0];
  let array2Item = array2[0];
  let i = 1;
  let j = 1;
  
  //We should actually move these 2 if statements to line 2 so that we do the checks before we do assignments in line 3 and 4!
  if(array1.length === 0) {
    return array2;
  }
  if(array2.length === 0) {
    return array1;
  }

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

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

Python solution

def merge_sorted_arrays(arr1, arr2):
    new_arr = []
    len1 = len(arr1)
    len2 = len(arr2)
    if len1 >= len2:
        arr_l = arr1
        arr_s = arr2
    else:
        arr_l = arr2
        arr_s = arr1
    while len(arr_s) != 0:
        if arr_l[0] < arr_s[0]:
            new_arr.append(arr_l[0])
            del arr_l[0]
        elif arr_l[0] > arr_s[0]:
            new_arr.append(arr_s[0])
            del arr_s[0]
        elif arr_l[0] == arr_s[0]:
            new_arr.append(arr_l[0])
            new_arr.append(arr_s[0])
            del arr_l[0]
            del arr_s[0]
    new_arr += arr_l
    return new_arr


arr1 = [0, 3, 4, 31]
arr2 = [4, 6, 30]
# arr1 = [1, 3, 5, 7, 9]
# arr2 = [2, 3, 4, 6]
# [1, 3, 5, 7, 9, 2, 3, 4, 6]
print(merge_sorted_arrays(arr1, arr2))

---

More Exercises:

• Two Sum
• Maximum Subarray
• Move Zeroes
• Contains Duplicate
• Rotate Array
• Longest Word

---

Array Pros:

• Fast lookups
• Fast push/pop
• Ordered

Array Cons:

• Slow inserts
• Slow deletes
• Fixed size (if using static array)