Data Structures
Arrays, Strings & Hash Maps
Arrays, Strings & Hash Maps Complexity Quick Reference Data Structure | Access | Search | Insert | Delete ------------------|--------|--------|--------|------- …
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 caseArrays — 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
}