Algorithms Lesson 2: Arrays

Arrays are the most fundamental data structure. Understanding array operations and their complexities is the foundation for everything else.

Array Complexities

// Access by index: O(1) — instant
arr[5];            // always constant time

// Search (unsorted): O(n) — must check every element
arr.indexOf(42);   // could be at end

// Insert at END: O(1) amortized
arr.push(42);

// Insert at BEGINNING: O(n) — shifts everything!
arr.unshift(42);   // all elements must move right

// Insert at MIDDLE: O(n)
arr.splice(3, 0, 42);

// Delete from END: O(1)
arr.pop();

// Delete from beginning: O(n)
arr.shift();

Two Pointers Pattern

// Find pair that sums to target in SORTED array
function twoSum(arr, target) {
  let left = 0, right = arr.length - 1;
  
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];  // found!
    else if (sum < target) left++;   // need bigger sum
    else right--;                    // need smaller sum
  }
  return null;
}
// O(n) time, O(1) space — much better than O(n²) brute force!

Sliding Window Pattern

// Find max sum subarray of size k
function maxSubarraySum(arr, k) {
  let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;
  
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum + arr[i] - arr[i - k]; // slide window!
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}
// O(n) — avoids recalculating sum from scratch