Common Data Structure Problems and Patterns

Why Practice Common Data Structure Problems?

Data structures become easier to understand when you apply them to problems. Instead of learning arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs as isolated concepts, problem solving shows how these structures are used to build efficient solutions.

Many coding problems also follow recurring patterns. Once you recognize the underlying pattern, you can often reduce a seemingly difficult problem into a smaller set of familiar operations.

Common Problem Categories

Common data structure problems can be grouped by the structure or technique they primarily use.

Array Problem: Find Duplicate Values

A common array problem is determining whether an array contains duplicate values. A simple approach compares every pair, but that requires quadratic time.

A set can track values that have already appeared.

function containsDuplicate(values) {
  const seen = new Set();

  for (const value of values) {
    if (seen.has(value)) {
      return true;
    }

    seen.add(value);
  }

  return false;
}

console.log(containsDuplicate([4, 8, 2, 8]));
// true

The expected time complexity is O(n), with O(n) additional space in the worst case.

Array Problem: Two Sum

The Two Sum pattern asks whether two values add up to a target. Instead of comparing every pair, a map can store values that have already been seen.

function twoSum(values, target) {
  const seen = new Map();

  for (let i = 0; i < values.length; i++) {
    const needed = target - values[i];

    if (seen.has(needed)) {
      return [seen.get(needed), i];
    }

    seen.set(values[i], i);
  }

  return [];
}

console.log(twoSum([2, 7, 11, 15], 9));
// [0, 1]

The map allows the algorithm to look for the required complement without scanning all previous values again. Its expected time complexity is O(n).

Array Problem: Maximum Subarray Sum

The maximum subarray problem asks for the contiguous portion of an array with the largest sum. A common linear-time solution uses Kadane's algorithm.

function maxSubarraySum(values) {
  let current = values[0];
  let best = values[0];

  for (let i = 1; i < values.length; i++) {
    current = Math.max(values[i], current + values[i]);
    best = Math.max(best, current);
  }

  return best;
}

console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
// 6

The algorithm keeps track of the best subarray ending at the current position and the best result found so far. It runs in O(n) time and uses O(1) extra space.

String Problem: Check for a Palindrome

A palindrome reads the same from both directions. A two-pointer technique can compare characters from the beginning and end while moving toward the center.

function isPalindrome(text) {
  let left = 0;
  let right = text.length - 1;

  while (left < right) {
    if (text[left] !== text[right]) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

console.log(isPalindrome('level'));
// true

The string is processed from both ends, giving O(n) time and O(1) additional space when character access is constant time.

String Problem: Check Whether Two Strings Are Anagrams

Two strings are anagrams when they contain the same characters with the same frequencies. A frequency map can represent the required counts.

function areAnagrams(first, second) {
  if (first.length !== second.length) {
    return false;
  }

  const counts = new Map();

  for (const char of first) {
    counts.set(char, (counts.get(char) || 0) + 1);
  }

  for (const char of second) {
    if (!counts.has(char)) {
      return false;
    }

    counts.set(char, counts.get(char) - 1);

    if (counts.get(char) < 0) {
      return false;
    }
  }

  return true;
}

console.log(areAnagrams('listen', 'silent'));
// true

Linked List Problem: Reverse a Linked List

Reversing a linked list is one of the most common pointer-manipulation problems. The iterative approach uses three references: the previous node, the current node, and the next node.

function reverseList(head) {
  let previous = null;
  let current = head;

  while (current !== null) {
    const next = current.next;

    current.next = previous;
    previous = current;
    current = next;
  }

  return previous;
}

Each node is processed once, so the time complexity is O(n) and the additional space complexity is O(1).

Linked List Problem: Detect a Cycle

A linked list may contain a cycle when a node eventually points back to an earlier node. Floyd's cycle detection algorithm uses slow and fast pointers.

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

The algorithm runs in O(n) time and uses O(1) additional space.

Linked List Problem: Merge Sorted Lists

When two linked lists are already sorted, they can be merged by comparing their current nodes and attaching the smaller node to the result.

List A: 1 → 4 → 7
List B: 2 → 3 → 8

Result: 1 → 2 → 3 → 4 → 7 → 8

function mergeLists(first, second) {
  const dummy = new Node(0);
  let current = dummy;

  while (first !== null && second !== null) {
    if (first.data <= second.data) {
      current.next = first;
      first = first.next;
    } else {
      current.next = second;
      second = second.next;
    }

    current = current.next;
  }

  current.next = first !== null ? first : second;

  return dummy.next;
}

The merge takes O(n + m) time for lists containing n and m nodes.

Stack Problem: Balanced Parentheses

A stack is a natural choice for checking whether opening and closing brackets are properly nested.

function isBalanced(text) {
  const stack = [];
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (const char of text) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

console.log(isBalanced('{[()]}'));
// true

Each character is processed once, resulting in O(n) time and O(n) worst-case space for the stack.

Stack Problem: Next Greater Element

The next greater element problem asks for the first value to the right of each element that is larger than it. A monotonic stack can avoid repeatedly scanning the remaining elements.

function nextGreaterElements(values) {
  const result = new Array(values.length).fill(-1);
  const stack = [];

  for (let i = values.length - 1; i >= 0; i--) {
    while (
      stack.length > 0 &&
      stack[stack.length - 1] <= values[i]
    ) {
      stack.pop();
    }

    if (stack.length > 0) {
      result[i] = stack[stack.length - 1];
    }

    stack.push(values[i]);
  }

  return result;
}

console.log(nextGreaterElements([4, 5, 2, 10]));
// [5, 10, 10, -1]

Although there is a nested loop, each element is pushed and removed from the stack at most once, giving an overall O(n) time complexity.

Queue Problem: Breadth-First Traversal

Breadth-first search processes nodes level by level. A queue maintains the order in which vertices should be processed.

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return order;
}

In production JavaScript, repeatedly using shift() can make queue operations less efficient. A head index can provide an efficient queue implementation for this pattern.

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  const order = [];
  let head = 0;

  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return order;
}

Tree Problem: Inorder Traversal

Tree traversal problems are common because they test recursion, stacks, and tree structure. Inorder traversal visits the left subtree, the current node, and then the right subtree.

function inorder(root, result = []) {
  if (root === null) {
    return result;
  }

  inorder(root.left, result);
  result.push(root.data);
  inorder(root.right, result);

  return result;
}

For a binary search tree, inorder traversal produces values in sorted order when the tree follows the standard BST ordering property.

Tree Problem: Find the Height

The height of a binary tree can be calculated recursively by finding the height of both subtrees and adding one for the current node.

function treeHeight(root) {
  if (root === null) {
    return 0;
  }

  const leftHeight = treeHeight(root.left);
  const rightHeight = treeHeight(root.right);

  return 1 + Math.max(leftHeight, rightHeight);
}

Every node is visited once, so the time complexity is O(n). The recursive call stack depends on the tree height.

Tree Problem: Search in a Binary Search Tree

A binary search tree provides an ordering that allows the search to choose either the left or right subtree at each step.

function searchBST(root, target) {
  let current = root;

  while (current !== null) {
    if (current.data === target) {
      return current;
    }

    if (target < current.data) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return null;
}

The complexity depends on the tree height. A balanced tree provides approximately O(log n) search, while a highly unbalanced tree can degrade to O(n).

Heap Problem: Find the Top K Elements

Heap-based problems often involve finding the largest or smallest few elements from a larger collection. A heap can maintain the relevant candidates without fully sorting every value.

For example, when searching for the largest k values, a min-heap of size k can keep the current top candidates.

Input:
[10, 4, 8, 20, 15, 3]

k = 3

Top 3:
20, 15, 10

The exact implementation depends on the language's available priority queue or heap support, but the general pattern is to maintain only the candidates that can still belong to the final result.

Hashing Problem: Frequency Counting

Frequency counting is one of the most reusable hash map patterns. It records how often each value occurs.

function countFrequency(values) {
  const frequency = new Map();

  for (const value of values) {
    frequency.set(
      value,
      (frequency.get(value) || 0) + 1
    );
  }

  return frequency;
}

const result = countFrequency([2, 4, 2, 5, 4, 2]);

console.log([...result]);
// [[2, 3], [4, 2], [5, 1]]

Frequency maps are useful for duplicate detection, anagram checking, counting occurrences, and many array and string problems.

Graph Problem: Detect Connectivity

A graph connectivity problem asks whether vertices are reachable from one another. Depth- first search or breadth-first search can explore the reachable portion of the graph.

function isReachable(graph, start, target) {
  const stack = [start];
  const visited = new Set();

  while (stack.length > 0) {
    const node = stack.pop();

    if (node === target) {
      return true;
    }

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);

    for (const neighbor of graph[node]) {
      stack.push(neighbor);
    }
  }

  return false;
}

With an adjacency list, a complete traversal generally takes O(V + E), where V is the number of vertices and E is the number of edges.

Graph Problem: Detect a Cycle

Cycle detection differs depending on whether the graph is directed or undirected. A common DFS-based approach tracks the current traversal path for directed graphs.

The important idea is to distinguish between a vertex that has already been completely processed and a vertex that is still part of the current DFS path.

Graph:

A → B → C
    ↑   |
    └───┘

The edge from C back to B creates a cycle.

Graph Problem: Shortest Path in an Unweighted Graph

In an unweighted graph, breadth-first search can find the shortest path measured by the number of edges from a starting vertex.

A ── B ── D
|         |
C ─────── E

Shortest path from A to D:

A → B → D

BFS explores vertices level by level, so the first time a vertex is reached gives the shortest number of edges from the starting point in an unweighted graph.

Common Problem-Solving Patterns

Several techniques appear repeatedly across data structure problems.

Two Pointers

Use two pointers when two positions in a sequence can be moved according to the problem's conditions. Common examples include palindrome checking, sorted pair problems, and linked list techniques.

Sliding Window

Sliding windows are useful when the problem concerns a contiguous range and the range can be expanded or contracted while maintaining useful state.

Hashing

Maps and sets are useful when repeated lookup, counting, grouping, or membership checking is required.

Fast and Slow Pointers

This pattern is especially useful for linked lists. It can detect cycles and can also be used to locate the middle of a linked list.

Monotonic Stack

A monotonic stack maintains elements in increasing or decreasing order and is useful for next greater element, next smaller element, and related range problems.

BFS and DFS

Breadth-first and depth-first traversal are fundamental techniques for trees and graphs. BFS naturally supports level-based processing, while DFS is useful for recursive exploration and connectivity-style problems.

How to Approach an Unfamiliar Problem

When you encounter a new data structure problem, avoid immediately searching for a memorized solution. Start by identifying what the problem requires.

1. Understand the input and expected output.
2. Write down the constraints.
3. Try a simple solution.
4. Identify repeated or expensive operations.
5. Choose a data structure that improves those operations.
6. Look for a known algorithmic pattern.
7. Analyze time and space complexity.
8. Test edge cases.

Edge Cases to Test

A solution should not only work for the main example. Test cases should include unusual inputs that exercise the boundaries of the algorithm.

• Empty input.
• One-element input.
• Duplicate values.
• All values identical.
• Already sorted input.
• Reverse-sorted input.
• Very large input.
• Negative values when permitted.
• Missing target values.
• Disconnected graph components.
• Single-node trees.
• Linked lists containing cycles.

Common Mistakes Across Data Structure Problems

• Choosing a data structure before understanding the required operations.
• Ignoring input constraints.
• Using nested loops when a hash-based lookup could remove repeated work.
• Forgetting to handle empty collections.
• Incorrect pointer updates in linked list problems.
• Failing to mark visited vertices during graph traversal.
• Confusing values with node or object references.
• Assuming a binary search tree is always balanced.
• Using BFS or DFS without considering the graph representation.
• Analyzing only time complexity and ignoring additional memory.

Build Pattern Recognition Through Practice

The goal of practicing common problems is not to memorize hundreds of solutions. Instead, group problems by the underlying technique.

Duplicate detection
        ↓
Hash Set

Two Sum
        ↓
Hash Map

Palindrome
        ↓
Two Pointers

Linked List Cycle
        ↓
Fast + Slow Pointers

Balanced Parentheses
        ↓
Stack

Shortest Path in Unweighted Graph
        ↓
BFS

Tree Traversal
        ↓
DFS / BFS

Recognizing the underlying technique makes it easier to adapt a known idea to a new problem.

A Practical Problem Set Structure

When learning data structures, practice problems progressively rather than starting with the most complex algorithms.

1. Basic traversal and access.
2. Insertion and deletion.
3. Searching and counting.
4. Hashing-based optimization.
5. Two-pointer problems.
6. Stack and queue problems.
7. Linked list pointer problems.
8. Tree traversal and recursion.
9. Heap and priority problems.
10. Graph traversal and path problems.

Key Takeaways

• Common data structure problems can be grouped by recurring patterns and techniques.
• Arrays frequently involve searching, duplicates, pairs, ranges, and subarrays.
• Hash maps and sets are useful for lookup, counting, grouping, and duplicate detection.
• Linked list problems commonly test pointer manipulation and fast/slow pointer techniques.
• Stacks are useful for nested structures, parentheses, undo behavior, and monotonic problems.
• Queues are important for FIFO processing and breadth-first traversal.
• Trees commonly involve recursion, DFS, BFS, height, and ordered searching.
• Heaps are useful when a problem repeatedly needs the highest- or lowest-priority item.
• Graphs commonly involve traversal, connectivity, cycle detection, dependencies, and shortest paths.
• Learning the underlying pattern is more useful than memorizing individual problem solutions.
• Always validate solutions with edge cases and analyze their time and space complexity.