DSA Fundamentals: Data Structures & Algorithms

Complexity, arrays, linked lists, trees, graphs, sorting and searching with examples.

Why data structures and algorithms matter

Data structures decide how data is stored and accessed; algorithms decide how operations are executed. The same problem can feel instant or painfully slow depending on these choices.

In interviews and real systems, you are often evaluated on correctness first, then scalability: does your solution still work when input size grows from 100 to 10 million?

Big-O intuition

O(1): constant time, independent of input size.
O(log n): divide-and-conquer steps, like binary search.
O(n): one full pass over data.
O(n log n): efficient comparison sorting family.
O(n^2): nested loops over same data, often too slow at scale.

Comparing linear vs binary search

function linearSearch(arr: number[], target: number): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // O(n)
  }
  return -1;
}

function binarySearch(sorted: number[], target: number): number {
  let left = 0;
  let right = sorted.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // O(log n)
}

Core patterns

Two pointers for sorted data and pair problems.
Sliding window for contiguous subarray/substring constraints.
Frequency map for counting characters and duplicates.
Prefix sums for fast range sum queries.

Sliding window example

Longest substring without repeating characters

function longestUniqueSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && (lastSeen.get(ch) ?? -1) >= left) {
      left = (lastSeen.get(ch) ?? 0) + 1;
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

Singly linked list essentials

A linked list stores nodes where each node points to the next node. Unlike arrays, insertion at head is O(1) and memory is non-contiguous.

Traversal: O(n)
Insert/Delete at head: O(1)
Search by value: O(n)

Fast and slow pointer

Detect cycle in linked list

type Node = { value: number; next: Node | null };

function hasCycle(head: Node | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow?.next ?? null;
    fast = fast.next.next;
    if (slow && fast && slow === fast) return true;
  }

  return false;
}

Choosing stack vs queue

Stack (LIFO): function calls, undo, expression parsing.
Queue (FIFO): scheduling, buffering, BFS traversal.
Use arrays for quick implementation, linked lists for strict O(1) ends.

Balanced brackets using stack

Parentheses validator

function isBalanced(expr: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

  for (const ch of expr) {
    if (["(", "[", "{"].includes(ch)) stack.push(ch);
    else if (pairs[ch]) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }

  return stack.length === 0;
}

Tree fundamentals

Binary tree node has up to two children.
Binary Search Tree (BST): left < node < right.
Depth-first traversals: preorder, inorder, postorder.
Breadth-first traversal uses a queue.

Recursive DFS traversal

Inorder traversal

type TreeNode = { value: number; left: TreeNode | null; right: TreeNode | null };

function inorder(root: TreeNode | null, out: number[] = []): number[] {
  if (!root) return out;
  inorder(root.left, out);
  out.push(root.value);
  inorder(root.right, out);
  return out;
}

How to model a graph

Graphs represent entities (nodes) and relationships (edges). They are used in maps, social networks, recommendation systems, and dependency graphs.

Adjacency list is memory efficient for sparse graphs.
BFS finds shortest path in unweighted graphs.
DFS is useful for connectivity and cycle checks.

BFS shortest distance

Distance from source in unweighted graph

function bfsDistance(graph: Record<string, string[]>, start: string): Record<string, number> {
  const distance: Record<string, number> = { [start]: 0 };
  const queue: string[] = [start];

  while (queue.length) {
    const node = queue.shift()!;
    for (const next of graph[node] ?? []) {
      if (distance[next] !== undefined) continue;
      distance[next] = distance[node] + 1;
      queue.push(next);
    }
  }

  return distance;
}

Algorithm trade-offs

Merge sort: O(n log n), stable, needs extra memory.
Quick sort: average O(n log n), in-place style, worst O(n^2).
Binary search needs sorted data and halves search space.

Merge sort implementation

Classic divide-and-conquer sort

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  const merged: number[] = [];

  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) merged.push(left[i++]);
    else merged.push(right[j++]);
  }

  return [...merged, ...left.slice(i), ...right.slice(j)];
}

Project goal

Build a mini toolkit that can run multiple DSA helpers: palindrome check, BFS shortest path, and top-K frequent elements. The focus is selecting the correct data structure per task.

Input parser and test runner.
Pattern tagging: array, graph, heap, tree.
Time/space complexity notes for each function.

Top-K frequent example

Extension: replace sorting with a heap for better performance when k << n.

Frequency map + sorting baseline

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);

  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([value]) => value);
}

Key Takeaways

Big-O is a communication tool for scalability, not just interview jargon.
Pick patterns quickly: sliding window, two pointers, stack, queue, DFS, BFS.
Mastering core structures makes unseen problems easier to decompose.
Always explain time and space complexity with trade-offs.
Projects help convert pattern recognition into implementation confidence.