Problems by Data Structure

Coding problems organized by data structure: arrays, linked lists, stacks, queues, trees, and graphs

Overview

This page organizes all coding problems by their underlying data structure. Each problem includes multiple solution approaches with detailed complexity analysis.

Source code location: /workspace/source/data-structures/

---

Arrays (7 Problems)

Arrays provide O(1) access but O(n) insertion and deletion. These problems explore various array manipulation techniques.

Problem 1: Rotate Matrix

Difficulty: Medium

Problem Statement: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees clockwise.

Example:

Input:
[1,  2,  3,  4,  5]
[6,  7,  8,  9,  10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20]
[21, 22, 23, 24, 25]

Output (rotated 90° clockwise):
[21, 16, 11, 6,  1]
[22, 17, 12, 7,  2]
[23, 18, 13, 8,  3]
[24, 19, 14, 9,  4]
[25, 20, 15, 10, 5]

Solution 1: New Matrix

Approach: Create a new matrix and copy elements in rotated positions.

Time Complexity: O(n²)

Space Complexity: O(n²)

Key Insight: For rotation, new[i][j] = old[n-1-j][i]

const n = matrix.length;
const result: number[][] = [];

for (let i = 0; i < n; i++) {
  for (let j = n - 1; j >= 0; j--) {
    if (!result[i]) {
      result[i] = [matrix[j][i]];
    } else {
      result[i].push(matrix[j][i]);
    }
  }
}

Solution 2: In-Place

Approach: Rotate layer by layer, swapping four elements at a time.

Time Complexity: O(n²)

Space Complexity: O(1)

Key Insight: Process in layers from outside to inside, swapping 4 elements per iteration.

for (let layer = 0; layer < n / 2; layer++) {
  const first = layer;
  const last = n - 1 - layer;
  
  for (let i = first; i < last; i++) {
    const offset = i - first;
    const top = matrix[first][i];
    
    // Rotate: left → top → right → bottom → left
    matrix[first][i] = matrix[last - offset][first];
    matrix[last - offset][first] = matrix[last][last - offset];
    matrix[last][last - offset] = matrix[i][last];
    matrix[i][last] = top;
  }
}

Source: /workspace/source/data-structures/array/array.problems.test.ts:5-76

Problem 2: Next Greater Element

Difficulty: Medium

Problem Statement: Given an array of integers with all distinct numbers, find the next greater element for each element. If no greater element exists to the right, return -1.

Example:

Input: [4, 5, 2, 25]
Output: [[4,5], [5,25], [2,25], [25,-1]]

Solution: Stack-Based

Approach: Use a stack to track elements awaiting their next greater element.

Time Complexity: O(n)

Space Complexity: O(n)

Algorithm:

1. Push first element to stack
2. For each subsequent element:
   • While stack is not empty and current > top: pair them
   • Push current element
3. Remaining stack elements pair with -1

const stack = new Stack();
const ans = [];

stack.push(arr[0]);

for (let i = 1; i < arr.length; i++) {
  while (!stack.isEmpty() && stack.peek()! < arr[i]) {
    ans.push([stack.pop(), arr[i]]);
  }
  stack.push(arr[i]);
}

while (!stack.isEmpty()) {
  ans.push([stack.pop(), -1]);
}

Source: /workspace/source/data-structures/array/array.problems.test.ts:78-109

Problem 3: Merge Sorted Arrays

Difficulty: Easy

Problem Statement: Given two sorted integer arrays nums1 and nums2, merge them into nums1 in-place. nums1 has enough space (size m+n) to hold both arrays.

Example:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Solution: Backward Merge

Approach: Compare elements from the end and place larger element at the back.

Time Complexity: O(n)

Space Complexity: O(1)

Key Insight: Working backwards avoids overwriting unprocessed elements.

let back = n + m - 1;
n--;
m--;

while (n >= 0) {
  if (m >= 0 && nums1[m] > nums2[n]) {
    nums1[back] = nums1[m];
    m--;
  } else {
    nums1[back] = nums2[n];
    n--;
  }
  back--;
}

Source: /workspace/source/data-structures/array/array.problems.test.ts:111-154

Problem 4: Find Number of Pairs

Difficulty: Medium

Problem Statement: Given two arrays X[] and Y[], find the number of pairs such that x^y > y^x where x is from X[] and y is from Y[].

Example:

Input: X = [2, 1, 6], Y = [1, 5]
Output: 3
Explanation: Pairs are (2,1), (2,5), and (6,1)

Solution: Brute Force

Approach: Compare all possible pairs.

Time Complexity: O(n × m)

Space Complexity: O(1)

let result = 0;

for (let x = 0; x < X.length; x++) {
  for (let y = 0; y < Y.length; y++) {
    if (Math.pow(X[x], Y[y]) > Math.pow(Y[y], X[x])) {
      result++;
    }
  }
}

Source: /workspace/source/data-structures/array/array.problems.test.ts:156-184

Problem 5: Array Difference

Difficulty: Easy

Problem Statement: Write a function that accepts two arrays and returns a new array containing all values not present in both arrays (symmetric difference).

Example:

Input: X = [1, 2, 3, 4], Y = [3, 4, 5, 6]
Output: [1, 2, 5, 6]

Solution: Hash Map

Approach: Use hash maps to track elements from both arrays.

Time Complexity: O(n)

Space Complexity: O(n)

const xMap = new Map(x.map((n) => [n, n]));
const yMap = new Map(y.map((n) => [n, n]));

return [
  ...x.filter((n) => !yMap.has(n)),
  ...y.filter((n) => !xMap.has(n)),
];

Source: /workspace/source/data-structures/array/array.problems.test.ts:186-207

Problem 6: Special Integer x

Difficulty: Medium

Problem Statement: Find the special integer x such that there are exactly x integers in array k that are greater than or equal to x. Return -1 if no such integer exists.

Example:

Input: k = [0, 4, 1, 0, 4]
Output: 2
Explanation: 2 values (4 and 4) are ≥ 2

Solution: Count Down

Approach: Check each value from max down to 0.

Time Complexity: O(m × n) where m is max value

Space Complexity: O(n)

const max = Math.max(...k);

for (let i = max - 1; i >= 0; i--) {
  let times = 0;
  for (let j = 0; j < k.length; j++) {
    if (k[j] >= i) times += 1;
  }
  if (i === times) return i;
}

return -1;

Source: /workspace/source/data-structures/array/array.problems.test.ts:209-239

Problem 7: Maximize Sum of Pair Minimums

Difficulty: Medium

Problem Statement: Given an array of N integers (N is even), group elements into pairs to maximize the sum of minimum values from each pair.

Example:

Input: [1, 5, 3, 2]
Output: 4
Explanation: Best pairing is (1,2) and (5,3) → min(1,2) + min(5,3) = 1 + 3 = 4

Solution: Sort First

Approach: Sort array, then sum elements at even indices.

Time Complexity: O(n log n)

Space Complexity: O(1)

Key Insight: After sorting, pair adjacent elements. The smaller of each pair is at even indices.

arr.sort((a, b) => a - b);

return arr.reduce((sum, num, i) => {
  if (i % 2 === 0) sum += num;
  return sum;
}, 0);

Source: /workspace/source/data-structures/array/array.problems.test.ts:241-267

---

Linked Lists (2 Problems)

Linked lists offer O(1) insertion/deletion but O(n) access. These problems explore pointer manipulation.

Problem 1: Partition List

Difficulty: Medium

Problem Statement: Partition a linked list around a value x such that all nodes less than x come before all nodes greater than or equal to x. The value x can appear anywhere in the right partition.

Example:

Input: 3 → 5 → 8 → 5 → 10 → 2 → 1, x = 5
Output: 1 → 2 → 3 → 5 → 8 → 5 → 10

Solution: In-Place Rearrangement

Approach: Move nodes less than x to the front while traversing.

Time Complexity: O(n)

Space Complexity: O(1)

let current = list.head;

for (let i = 0; current?.next; i++) {
  const next = current.next;
  
  if (current.next.value < x) {
    current.next = next.next;
    
    // Move to front
    const temp = list.head;
    list.head = next;
    next.next = temp;
  } else {
    current = next;
  }
}

Source: /workspace/source/data-structures/lists/singly-linked-list/singly-linked-list.problems.test.ts:5-43

Problem 2: Sum Lists

Difficulty: Medium

Problem Statement: Given two numbers represented by linked lists where each node contains a single digit stored in reverse order, add them and return the sum as a linked list.

Example:

Input: (7 → 1 → 6) + (5 → 9 → 2)
       Represents: 617 + 295
Output: (2 → 1 → 9)
        Represents: 912

Solution: Digit-by-Digit Addition

Approach: Traverse both lists, add corresponding digits, track carry.

Time Complexity: O(max(n, m))

Space Complexity: O(max(n, m))

let current1 = n1.head;
let current2 = n2.head;
let carry = 0;

while (current1) {
  if (current2) {
    carry = current1.value + current2.value + carry;
    
    if (carry >= 10) {
      output.push(carry % 10);
      carry = Math.floor(carry / 10);
    } else {
      output.push(carry);
      carry = 0;
    }
    
    current1 = current1.next;
    current2 = current2.next;
  } else {
    output.push(current1.value + carry);
    current1 = current1.next;
    carry = 0;
  }
}

Source: /workspace/source/data-structures/lists/singly-linked-list/singly-linked-list.problems.test.ts:45-94

---

Stacks (2 Problems)

Stacks use LIFO ordering and provide O(1) push/pop operations.

Problem 1: Sort Stack

Difficulty: Medium

Problem Statement: Sort a stack in ascending order (smallest items on top) using at most one additional stack. You may not copy elements into any other data structure.

Example:

Input: [4][2][1][3]  (top to bottom)
Output: [1][2][3][4]  (top to bottom)

Solution: Auxiliary Stack

Approach: Use a second stack to temporarily hold sorted elements.

Time Complexity: O(n²)

Space Complexity: O(n)

Algorithm:

1. Pop element from original stack
2. While aux stack top < element, move aux elements back to original
3. Push element to aux stack
4. Repeat until original is empty
5. Move all back to original

const auxStack = new Stack();

while (!stack.isEmpty()) {
  const temp = stack.pop();
  
  while (!auxStack.isEmpty() && temp! > auxStack.peek()!) {
    stack.push(auxStack.pop()!);
  }
  
  auxStack.push(temp!);
}

while (!auxStack.isEmpty()) {
  stack.push(auxStack.pop()!);
}

Source: /workspace/source/data-structures/stack/stack.problems.test.ts:5-38

Problem 2: Base Converter

Difficulty: Easy

Problem Statement: Write a converter from decimal to bases between 2 and 36.

Example:

Input: baseConverter(10, 2)
Output: "1010"

Input: baseConverter(100345, 16)
Output: "187F9"

Solution: Division Method

Approach: Repeatedly divide by base, push remainders to stack, then pop to build result.

Time Complexity: O(log n)

Space Complexity: O(log n)

const stack = new Stack();
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

while (num) {
  const rem = Math.floor(num % base);
  stack.push(rem);
  num = Math.floor(num / base);
}

let output = '';
while (!stack.isEmpty()) {
  output += digits[stack.pop()!];
}

return output;

Source: /workspace/source/data-structures/stack/stack.problems.test.ts:40-69

---

Trees (4 Problems)

Trees are hierarchical structures. These problems explore traversal, serialization, and level-based operations.

Problem 1: Right View of Binary Tree

Difficulty: Medium

Problem Statement: Given a binary tree, print the right view - the set of nodes visible when viewing the tree from the right side.

Example:

Input:
       1
     /   \
    2     3
   / \   / \
  4   5 6   7
           \
            8

Output: [1, 3, 7, 8]

Solution 1: DFS with Hash Map

Approach: Use pre-order traversal, storing the last node at each level.

Time Complexity: O(n)

Space Complexity: O(h) where h is height

Key Insight: Since we traverse right subtree after left, the last value stored at each level is the rightmost.

function traverse(
  node: Node | null,
  level: number,
  map: Record<number, number>
) {
  if (node === null) return;
  
  // Overwrites with latest value at level (rightmost)
  map[level] = node.value;
  
  traverse(node.leftNode, level + 1, map);
  traverse(node.rightNode, level + 1, map);
}

const output = {};
traverse(root, 1, output);

Solution 2: BFS

Approach: Use level-order traversal with a queue.

Time Complexity: O(n + m)

Space Complexity: O(n)

const queue = new Queue<Node>();
const output = [];

queue.enqueue(root);

while (!queue.isEmpty()) {
  let count = queue.size;
  
  while (count > 0) {
    const node = queue.dequeue();
    count -= 1;
    
    // Only push rightmost node
    if (count === 0) {
      output.push(node?.value);
    }
    
    if (node?.leftNode) queue.enqueue(node.leftNode);
    if (node?.rightNode) queue.enqueue(node.rightNode);
  }
}

Source: /workspace/source/data-structures/trees/tree/tree.problems.test.ts:6-99

Problem 2: Binary Tree Height

Difficulty: Easy

Problem Statement: Calculate the height of a binary tree. Height of an empty tree is -1, height of a tree with one node is 0.

Example:

Input:
     1
    / \
   2   3
  / \
 4   5

Output: 2

Solution: Recursive DFS

Approach: Recursively find max depth of left and right subtrees.

Time Complexity: O(n)

Space Complexity: O(h) where h is height

function traverse(node: Node | null, levels: number): number {
  if (node === null) return levels;
  
  levels += 1;
  
  return Math.max(
    traverse(node.leftNode, levels),
    traverse(node.rightNode, levels)
  );
}

const height = traverse(root, -1);

Source: /workspace/source/data-structures/trees/tree/tree.problems.test.ts:101-142

Problem 3: Connect Nodes at Same Level

Difficulty: Medium

Problem Statement: Connect all adjacent nodes at the same level in a binary tree using a nextRight pointer.

Example:

Input:
     A
    / \
   B   C
  / \   \
 D   E   F

Output:
     A--->null
    / \
   B-->C-->null
  / \   \
 D-->E-->F-->null

Solution: Level Tracking

Approach: Use a hash map to track the last node at each level.

Time Complexity: O(n)

Space Complexity: O(h)

const map: Record<number, ConnectedNode<string>> = {};

function traverse(node: ConnectedNode<string> | null, level: number = 0) {
  if (node === null) return;
  
  if (map[level]) {
    map[level].nextRight = node;
  }
  
  map[level] = node;
  
  traverse(node.leftNode, level + 1);
  traverse(node.rightNode, level + 1);
}

traverse(root);

Source: /workspace/source/data-structures/trees/tree/tree.problems.test.ts:144-213

Problem 4: Serialize and Deserialize Binary Tree

Difficulty: Hard

Problem Statement: Implement functions to serialize a binary tree into a string and deserialize the string back into the tree.

Example:

Input:
     1
    / \
   2   3
  / \ / \
 4  5 6  7

Serialized: "1,2,4,#,#,5,#,#,3,6,#,#,7,#,#"

Solution: Pre-order Traversal

Approach: Use pre-order traversal with ’#’ for null nodes.

Time Complexity: O(n) for both operations

Space Complexity: O(n)

function serialize(node: Node<number> | null, str: string = "") {
  if (node === null) {
    return str ? `${str},#` : "#";
  }
  
  str = str ? `${str},${node.value}` : `${node.value}`;
  str = serialize(node.leftNode, str) + "," + serialize(node.rightNode);
  
  return str;
}

function deserialize(root: Node<number> | null, str: string[]) {
  const val = str.shift();
  
  if (!val || val === "#") return null;
  
  root = new Node<number>(Number(val));
  root.leftNode = deserialize(root.leftNode, str);
  root.rightNode = deserialize(root.rightNode, str);
  
  return root;
}

Source: /workspace/source/data-structures/trees/tree/tree.problems.test.ts:215-270

---

Queues

No queue-specific problems are currently implemented in the repository. However, queues are used extensively in BFS algorithms (see Tree Problem 1) and form the basis for many scheduling and traversal problems.

Source: /workspace/source/data-structures/queue/queue.problems.test.ts

---

Graphs

No graph-specific problems are currently implemented in the repository. However, the graph data structure is fully implemented and can be used for problems like DFS, BFS, shortest path, and cycle detection.

Source: /workspace/source/data-structures/graph/graph.problems.test.ts

---

Quick Reference

Arrays

7 problems covering matrix operations, searching, and optimization

Linked Lists

2 problems on partitioning and arithmetic operations

Stacks

2 problems demonstrating LIFO principles

Queues

No problems currently implemented - see Tree problems for queue usage in BFS

Trees

4 problems on traversal, serialization, and level operations

Graphs

No problems currently implemented - graph data structure available