Arrays, Strings & Hash Maps

Complexity Quick Reference

Data Structure    | Access | Search | Insert | Delete
------------------|--------|--------|--------|-------
Array             |  O(1)  |  O(n)  |  O(n)  |  O(n)
Dynamic Array     |  O(1)  |  O(n)  |  O(1)* |  O(n)
Linked List       |  O(n)  |  O(n)  |  O(1)  |  O(1)
Hash Map/Set      |   -    |  O(1)* |  O(1)* |  O(1)*
Binary Search Tree|  O(h)  |  O(h)  |  O(h)  |  O(h)
Balanced BST      | O(log) | O(log) | O(log) | O(log)
Heap (max/min)    |   -    |  O(n)  | O(log) | O(log)
Stack             |   -    |  O(n)  |  O(1)  |  O(1)
Queue             |   -    |  O(n)  |  O(1)  |  O(1)

* amortized or average case

Arrays — Common Patterns

// Two Pointers — O(n)
function twoSum(nums: number[], target: number): [number, number] | null {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return null;
}

// Sliding Window — O(n)
function maxSumSubarray(nums: number[], k: number): number {
  let windowSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// Prefix Sum — O(n) precompute, O(1) range query
function buildPrefix(nums: number[]): number[] {
  const prefix = [0];
  for (const n of nums) prefix.push(prefix[prefix.length - 1] + n);
  return prefix;
}
function rangeSum(prefix: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left];
}

// Kadane's Algorithm — max subarray sum O(n)
function maxSubarraySum(nums: number[]): number {
  let maxSum = nums[0], currentSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Hash Map Patterns

// Frequency counter
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const freq = new Map<string, number>();
  for (const c of s) freq.set(c, (freq.get(c) ?? 0) + 1);
  for (const c of t) {
    const count = freq.get(c);
    if (!count) return false;
    freq.set(c, count - 1);
  }
  return true;
}

// Two-sum using hash map — O(n) time, O(n) space
function twoSumUnsorted(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>();  // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement)!, i];
    seen.set(nums[i], i);
  }
  return null;
}

// Group anagrams
function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    const group = groups.get(key) ?? [];
    group.push(s);
    groups.set(key, group);
  }
  return [...groups.values()];
}

Linked List

class ListNode {
  constructor(public val: number, public next: ListNode | null = null) {}
}

// Reverse linked list — O(n) time, O(1) space
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

// Detect cycle — Floyd's algorithm
function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

// Find middle node (fast/slow pointers)
function findMiddle(head: ListNode): ListNode {
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  return slow;  // slow is at middle
}