Data Structure Interview Questions with Answers
Most Asked Data Structure Interview Questions for Software Engineer Roles
Introduction
Data Structures are fundamental concepts in Computer Science and play a crucial role in solving complex problems efficiently. In this page, we cover the most asked Data Structure interview questions with detailed answers, code examples, and key insights to help you ace your technical interviews.
Why Data Structures?
- Helps solve problems efficiently
- Builds strong problem-solving skills
- Improves memory and time optimization
- Used in real-world software development
- Essential for technical interviews
Most Asked Data Structure Interview Questions
A Data Structure is a way of organizing and storing data so that it can be accessed and modified efficiently.
Different data structures are used for different purposes depending on the type of operations required.
Data structures help improve performance, memory management, and problem-solving in software applications.
Main Types of Data Structures- Linear Data Structures
- Non-Linear Data Structures
- Static Data Structures
- Dynamic Data Structures
An Array is a linear data structure used to store multiple values in a single variable.
Array elements are stored in contiguous memory locations and accessed using indexes.
Advantages- Fast access using index
- Easy traversal
- Efficient memory usage
const numbers = [10, 20, 30, 40];
console.log(numbers[0]);
numbers.push(50);
console.log(numbers);A Linked List is a linear data structure where each element is called a node.
Each node contains data and a pointer to the next node in the sequence.
Advantages- Dynamic size
- Efficient insertion
- Efficient deletion
- No memory wastage
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
const first = new Node(10);
const second = new Node(20);
first.next = second;
console.log(first);Stack is a linear data structure that follows the LIFO principle.
LIFO means Last In First Out.
Real-Life Examples- Undo functionality
- Browser history
- Function call stack
- Expression evaluation
const stack = [];
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.pop());
console.log(stack);Queue is a linear data structure that follows the FIFO principle.
FIFO means First In First Out.
Use Cases- Task scheduling
- Printer queue
- Call center systems
- CPU scheduling
const queue = [];
queue.push("A");
queue.push("B");
queue.push("C");
console.log(queue.shift());
console.log(queue);A Hash Table is a data structure that stores data in key-value pairs.
It uses a hash function to calculate the index where data is stored.
Advantages- Fast searching
- Fast insertion
- Fast deletion
- Efficient data lookup
const user = {
id: 1,
name: "AK",
city: "Delhi"
};
console.log(user.name);
console.log(user.city);A Tree is a hierarchical non-linear data structure consisting of nodes.
The top node is called the root node and child nodes are connected below it.
Applications- File systems
- Databases
- HTML DOM
- Search algorithms
class TreeNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(20);
console.log(root);Binary Search is an efficient searching algorithm used on sorted arrays.
It repeatedly divides the search space into two halves.
Advantages- Fast searching
- Efficient for large datasets
- Reduces comparisons
- Time Complexity O(log n)
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
console.log(binarySearch([1,2,3,4,5], 4));A Graph is a non-linear data structure consisting of nodes and edges.
Graphs are used to represent relationships between different objects.
Real-Life Examples- Social networks
- Google Maps
- Flight routes
- Recommendation systems
const graph = {
A: ["B", "C"],
B: ["D"],
C: [],
D: []
};
console.log(graph["A"]);Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.
It continues until the array is fully sorted, bubbling the largest element to the end in each pass.
Characteristics- Time Complexity O(n²)
- Space Complexity O(1)
- Stable sorting algorithm
- In-place sorting
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
console.log(bubbleSort([5, 3, 8, 1, 2]));Selection Sort works by selecting the minimum element from the unsorted part and placing it at the beginning.
This process repeats for every position until the array is sorted.
Characteristics- Time Complexity O(n²)
- Space Complexity O(1)
- Not stable
- In-place sorting
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
let temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
return arr;
}
console.log(selectionSort([64, 25, 12, 22, 11]));Insertion Sort builds the sorted array one element at a time by inserting each element into its correct position.
It is efficient for small datasets and nearly sorted arrays.
Characteristics- Time Complexity O(n²)
- Best Case O(n)
- Stable sorting algorithm
- Efficient for small data
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
console.log(insertionSort([12, 11, 13, 5, 6]));Merge Sort is a divide and conquer algorithm that splits the array into halves, sorts them, and merges them back.
It is one of the most efficient sorting algorithms for large datasets.
Characteristics- Time Complexity O(n log n)
- Space Complexity O(n)
- Stable sorting algorithm
- Divide and conquer approach
function mergeSort(arr) {
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));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9]));Quick Sort is a divide and conquer algorithm that selects a pivot and partitions the array around it.
Elements smaller than the pivot go left, larger go right, and the process repeats recursively.
Characteristics- Average Time Complexity O(n log n)
- Worst Case O(n²)
- In-place sorting
- Not stable
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1];
const left = arr.slice(0, -1).filter(x => x <= pivot);
const right = arr.slice(0, -1).filter(x => x > pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([10, 7, 8, 9, 1, 5]));Recursion is a programming technique where a function calls itself to solve a smaller subproblem.
Every recursive function must have a base case to stop infinite recursion.
Use Cases- Tree traversal
- Factorial calculation
- Fibonacci series
- Divide and conquer
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}
console.log(factorial(5));The Fibonacci Series is a sequence where each number is the sum of the two preceding numbers.
It starts with 0 and 1: 0, 1, 1, 2, 3, 5, 8, 13...
Applications- Dynamic programming problems
- Golden ratio calculations
- Algorithm complexity analysis
- Nature patterns
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(7));BFS is a graph traversal algorithm that explores all neighbors of a node before moving to the next level.
It uses a queue data structure to keep track of nodes to visit.
Applications- Shortest path finding
- Social network friend suggestions
- Web crawlers
- Level order tree traversal
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
visited.add(start);
while (queue.length > 0) {
const node = queue.shift();
console.log(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
const graph = { A: ["B","C"], B: ["D"], C: [], D: [] };
bfs(graph, "A");DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
It uses a stack (or recursion) to keep track of the path.
Applications- Cycle detection
- Topological sorting
- Maze solving
- Connected components
function dfs(graph, node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
console.log(node);
for (const neighbor of graph[node]) {
dfs(graph, neighbor, visited);
}
}
const graph = { A: ["B","C"], B: ["D"], C: [], D: [] };
dfs(graph, "A");A Doubly Linked List is a linked list where each node has pointers to both the next and the previous node.
This allows traversal in both directions unlike a singly linked list.
Advantages- Bidirectional traversal
- Efficient deletion
- Easier reverse traversal
- Used in browser history
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
const a = new Node(1);
const b = new Node(2);
a.next = b;
b.prev = a;
console.log(a);
console.log(b);A Circular Linked List is a linked list where the last node points back to the first node.
This forms a circle so there is no null at the end.
Use Cases- Round robin scheduling
- Music playlists
- Circular buffers
- Token ring networks
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
const first = new Node(1);
const second = new Node(2);
const third = new Node(3);
first.next = second;
second.next = third;
third.next = first;
console.log(first.next.next.next.data);A Min Heap is a complete binary tree where the parent node is always smaller than or equal to its children.
The minimum element is always at the root, allowing O(1) access to it.
Applications- Priority queues
- Dijkstra's algorithm
- Heap sort
- Scheduling systems
class MinHeap {
constructor() { this.heap = []; }
insert(val) {
this.heap.push(val);
this.heap.sort((a, b) => a - b);
}
extractMin() {
return this.heap.shift();
}
}
const h = new MinHeap();
h.insert(5);
h.insert(1);
h.insert(3);
console.log(h.extractMin());A Max Heap is a complete binary tree where the parent node is always greater than or equal to its children.
The maximum element is always at the root, allowing O(1) access to it.
Applications- Priority queues
- Heap sort
- Finding Kth largest element
- Job scheduling
class MaxHeap {
constructor() { this.heap = []; }
insert(val) {
this.heap.push(val);
this.heap.sort((a, b) => b - a);
}
extractMax() {
return this.heap.shift();
}
}
const h = new MaxHeap();
h.insert(5);
h.insert(1);
h.insert(9);
console.log(h.extractMax());A Trie is a tree-like data structure used to store strings where each node represents a character.
It is primarily used for efficient prefix-based searching and autocomplete features.
Applications- Autocomplete
- Spell checker
- IP routing
- Dictionary implementation
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) node.children[ch] = new TrieNode();
node = node.children[ch];
}
node.isEnd = true;
}
search(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) return false;
node = node.children[ch];
}
return node.isEnd;
}
}
const trie = new Trie();
trie.insert("hello");
console.log(trie.search("hello"));A HashMap in JavaScript is implemented using the Map object which stores key-value pairs.
Unlike plain objects, Map allows any data type as a key and maintains insertion order.
Advantages- O(1) average lookup
- Any type can be a key
- Maintains insertion order
- Built-in size property
const map = new Map();
map.set("name", "Alice");
map.set("age", 25);
console.log(map.get("name"));
console.log(map.has("age"));
console.log(map.size);A Set is a collection of unique values in JavaScript. Duplicate values are automatically ignored.
Sets provide efficient operations for adding, removing, and checking the existence of elements.
Advantages- No duplicate values
- O(1) lookup time
- Easy to remove duplicates from arrays
- Built-in iteration support
const set = new Set();
set.add(1);
set.add(2);
set.add(2);
set.add(3);
console.log(set.size);
console.log(set.has(2));Linear Search is the simplest searching algorithm that checks each element one by one until the target is found.
It works on both sorted and unsorted arrays.
Characteristics- Time Complexity O(n)
- Works on unsorted data
- Simple to implement
- Inefficient for large datasets
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
console.log(linearSearch([4, 2, 7, 1, 9], 7));Heap Sort uses a binary heap data structure to sort elements. It first builds a max heap then extracts elements.
It is an in-place algorithm with guaranteed O(n log n) time complexity.
Characteristics- Time Complexity O(n log n)
- Space Complexity O(1)
- Not stable
- In-place sorting
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
const l = 2 * i + 1;
const r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
console.log(heapSort([12, 11, 13, 5, 6, 7]));Counting Sort is a non-comparison based sorting algorithm that counts the occurrences of each element.
It is efficient when the range of input values is not significantly larger than the number of elements.
Characteristics- Time Complexity O(n + k)
- Space Complexity O(k)
- Stable sorting algorithm
- Best for integer data
function countingSort(arr) {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
const output = [];
for (const num of arr) count[num]++;
for (let i = 0; i <= max; i++) {
while (count[i]-- > 0) output.push(i);
}
return output;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));A Deque (Double-Ended Queue) is a data structure that allows insertion and deletion from both ends.
It combines the features of both stacks and queues.
Use Cases- Sliding window problems
- Undo/redo operations
- Palindrome checking
- Task scheduling
const deque = [];
deque.push("B");
deque.unshift("A");
deque.push("C");
console.log(deque.shift());
console.log(deque.pop());
console.log(deque);A Priority Queue is a data structure where each element has a priority and elements with higher priority are served first.
It is usually implemented using a heap for efficient operations.
Applications- Dijkstra's shortest path
- CPU task scheduling
- Huffman coding
- A* search algorithm
class PriorityQueue {
constructor() { this.items = []; }
enqueue(item, priority) {
this.items.push({ item, priority });
this.items.sort((a, b) => a.priority - b.priority);
}
dequeue() {
return this.items.shift().item;
}
}
const pq = new PriorityQueue();
pq.enqueue("Task A", 2);
pq.enqueue("Task B", 1);
pq.enqueue("Task C", 3);
console.log(pq.dequeue());An AVL Tree is a self-balancing Binary Search Tree where the height difference between left and right subtrees is at most 1.
It automatically rebalances itself after insertions and deletions using rotations.
Properties- Balance factor is -1, 0, or 1
- Search in O(log n)
- Always balanced
- Uses rotations for balancing
class AVLNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
this.height = 1;
}
}
function getHeight(node) {
return node ? node.height : 0;
}
function getBalance(node) {
return node ? getHeight(node.left) - getHeight(node.right) : 0;
}
console.log("AVL Tree node created");A BST is a binary tree where the left child is smaller than the parent and the right child is greater.
This property allows efficient searching, insertion, and deletion operations.
Operations- Search O(log n) average
- Insert O(log n) average
- Delete O(log n) average
- Inorder traversal gives sorted output
class BSTNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BST {
constructor() { this.root = null; }
insert(data) {
const node = new BSTNode(data);
if (!this.root) { this.root = node; return; }
let curr = this.root;
while (true) {
if (data < curr.data) {
if (!curr.left) { curr.left = node; return; }
curr = curr.left;
} else {
if (!curr.right) { curr.right = node; return; }
curr = curr.right;
}
}
}
}
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(20);
console.log(bst.root);Inorder Traversal visits nodes in the order: Left → Root → Right.
For a BST, inorder traversal produces elements in sorted ascending order.
Properties- Produces sorted output for BST
- Time Complexity O(n)
- Uses recursion or stack
- Visits every node exactly once
function inorder(node) {
if (!node) return;
inorder(node.left);
console.log(node.data);
inorder(node.right);
}
const root = { data: 10, left: { data: 5, left: null, right: null }, right: { data: 20, left: null, right: null } };
inorder(root);Preorder Traversal visits nodes in the order: Root → Left → Right.
It is used to create a copy of the tree or serialize tree structure.
Use Cases- Tree serialization
- Creating tree copies
- Prefix expression evaluation
- Directory listing
function preorder(node) {
if (!node) return;
console.log(node.data);
preorder(node.left);
preorder(node.right);
}
const root = { data: 10, left: { data: 5, left: null, right: null }, right: { data: 20, left: null, right: null } };
preorder(root);Postorder Traversal visits nodes in the order: Left → Right → Root.
It is used to delete a tree safely or evaluate postfix expressions.
Use Cases- Tree deletion
- Postfix expression evaluation
- Computing directory sizes
- Dependency resolution
function postorder(node) {
if (!node) return;
postorder(node.left);
postorder(node.right);
console.log(node.data);
}
const root = { data: 10, left: { data: 5, left: null, right: null }, right: { data: 20, left: null, right: null } };
postorder(root);Dynamic Programming is an optimization technique that solves complex problems by breaking them into overlapping subproblems.
It stores results of subproblems to avoid redundant computations, using memoization or tabulation.
Key Concepts- Optimal substructure
- Overlapping subproblems
- Memoization (top-down)
- Tabulation (bottom-up)
function fib(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
console.log(fib(10));The 0/1 Knapsack Problem involves selecting items with given weights and values to maximize total value within a weight limit.
Each item can either be taken (1) or left (0), hence the name 0/1 Knapsack.
Approach- Solved using dynamic programming
- Time Complexity O(n*W)
- Space Complexity O(n*W)
- Classic DP problem
function knapsack(weights, values, W, n) {
if (n === 0 || W === 0) return 0;
if (weights[n - 1] > W) return knapsack(weights, values, W, n - 1);
return Math.max(
values[n - 1] + knapsack(weights, values, W - weights[n - 1], n - 1),
knapsack(weights, values, W, n - 1)
);
}
const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
console.log(knapsack(weights, values, 7, 4));The Longest Common Subsequence (LCS) finds the longest subsequence present in both given strings.
A subsequence maintains relative order but does not require contiguous elements.
Applications- DNA sequence analysis
- File diff tools
- Version control systems
- Text comparison
function lcs(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
console.log(lcs("ABCBDAB", "BDCAB"));Dijkstra's Algorithm finds the shortest path from a source node to all other nodes in a weighted graph.
It uses a greedy approach with a priority queue to always process the nearest unvisited node.
Properties- Works only with non-negative weights
- Time Complexity O((V+E) log V)
- Used in GPS navigation
- Network routing protocols
function dijkstra(graph, start) {
const dist = {};
const visited = new Set();
for (const node in graph) dist[node] = Infinity;
dist[start] = 0;
while (visited.size < Object.keys(graph).length) {
const node = Object.keys(dist)
.filter(n => !visited.has(n))
.reduce((a, b) => dist[a] < dist[b] ? a : b);
visited.add(node);
for (const [neighbor, weight] of graph[node]) {
if (dist[node] + weight < dist[neighbor]) {
dist[neighbor] = dist[node] + weight;
}
}
}
return dist;
}
const graph = { A: [["B", 1], ["C", 4]], B: [["C", 2], ["D", 5]], C: [["D", 1]], D: [] };
console.log(dijkstra(graph, "A"));A Segment Tree is a tree data structure used for storing information about intervals or segments of an array.
It allows efficient range queries and point updates in O(log n) time.
Applications- Range sum queries
- Range minimum/maximum
- Interval updates
- Competitive programming
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) { this.tree[node] = arr[start]; return; }
const mid = Math.floor((start + end) / 2);
this.build(arr, 2*node+1, start, mid);
this.build(arr, 2*node+2, mid+1, end);
this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
}
query(node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return this.tree[node];
const mid = Math.floor((start + end) / 2);
return this.query(2*node+1, start, mid, l, r) + this.query(2*node+2, mid+1, end, l, r);
}
}
const st = new SegmentTree([1, 3, 5, 7, 9, 11]);
console.log(st.query(0, 0, 5, 1, 3));Bit Manipulation involves performing operations directly on binary representations of numbers.
It is used for performance optimization and solving problems related to binary data efficiently.
Common Operations- AND, OR, XOR, NOT
- Left shift and right shift
- Setting and clearing bits
- Checking even or odd
const a = 5; // 101
const b = 3; // 011
console.log(a & b); // AND
console.log(a | b); // OR
console.log(a ^ b); // XOR
console.log(~a); // NOT
console.log(a << 1); // Left shift
console.log(a >> 1); // Right shiftThe Two Pointer Technique uses two pointers that move through the data structure to solve problems efficiently.
It is commonly used on sorted arrays to reduce time complexity from O(n²) to O(n).
Use Cases- Two sum problem
- Removing duplicates
- Container with most water
- Palindrome checking
function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
else if (sum < target) left++;
else right--;
}
return [];
}
console.log(twoSum([1, 2, 3, 4, 6], 6));The Sliding Window Technique maintains a window of elements and slides it across the array to find optimal subsets.
It reduces nested loop complexity by reusing computations from the previous window.
Use Cases- Maximum sum subarray of size k
- Longest substring without repeating characters
- Minimum window substring
- Count occurrences of anagrams
function maxSubarraySum(arr, k) {
let maxSum = 0;
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += arr[i];
maxSum = windowSum;
for (let i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3));Kadane's Algorithm finds the maximum sum contiguous subarray in O(n) time.
It uses dynamic programming by tracking the current sum and updating the maximum sum at each step.
Properties- Time Complexity O(n)
- Space Complexity O(1)
- Handles all negative arrays
- Classic DP greedy problem
function maxSubarray(arr) {
let maxSum = arr[0];
let currentSum = arr[0];
for (let i = 1; i < arr.length; i++) {
currentSum = Math.max(arr[i], currentSum + arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));Floyd-Warshall Algorithm finds the shortest paths between all pairs of vertices in a weighted graph.
It works with both positive and negative edge weights but not negative cycles.
Properties- Time Complexity O(V³)
- Space Complexity O(V²)
- All-pairs shortest path
- Dynamic programming approach
function floydWarshall(graph) {
const dist = graph.map(row => [...row]);
const n = dist.length;
for (let k = 0; k < n; k++)
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
return dist;
}
const INF = Infinity;
const graph = [
[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]
];
console.log(floydWarshall(graph));Prim's Algorithm finds the Minimum Spanning Tree (MST) of a weighted undirected graph.
It greedily adds the cheapest edge connecting an unvisited vertex to the current MST.
Properties- Works on dense graphs
- Time Complexity O(V²)
- Greedy algorithm
- Produces minimum cost spanning tree
function primMST(graph) {
const n = graph.length;
const inMST = new Array(n).fill(false);
const key = new Array(n).fill(Infinity);
key[0] = 0;
let cost = 0;
for (let count = 0; count < n; count++) {
let u = -1;
for (let v = 0; v < n; v++)
if (!inMST[v] && (u === -1 || key[v] < key[u])) u = v;
inMST[u] = true;
cost += key[u];
for (let v = 0; v < n; v++)
if (graph[u][v] && !inMST[v] && graph[u][v] < key[v])
key[v] = graph[u][v];
}
return cost;
}
const graph = [[0,2,0,6,0],[2,0,3,8,5],[0,3,0,0,7],[6,8,0,0,9],[0,5,7,9,0]];
console.log(primMST(graph));Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) where every edge goes from left to right.
It is used in scheduling tasks that have dependencies on each other.
Applications- Build systems
- Task scheduling
- Course prerequisites
- Package dependency resolution
function topologicalSort(graph) {
const visited = new Set();
const stack = [];
function dfs(node) {
visited.add(node);
for (const neighbor of (graph[node] || [])) {
if (!visited.has(neighbor)) dfs(neighbor);
}
stack.push(node);
}
for (const node in graph) {
if (!visited.has(node)) dfs(node);
}
return stack.reverse();
}
const graph = { A: ["C"], B: ["C", "D"], C: ["E"], D: ["F"], E: [], F: [] };
console.log(topologicalSort(graph));Union-Find is a data structure that tracks elements split into disjoint (non-overlapping) sets.
It supports two operations: Find (which set an element belongs to) and Union (merge two sets).
Applications- Cycle detection in graphs
- Kruskal's MST algorithm
- Network connectivity
- Image segmentation
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
const px = this.find(x), py = this.find(y);
if (px === py) return;
if (this.rank[px] < this.rank[py]) this.parent[px] = py;
else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
else { this.parent[py] = px; this.rank[px]++; }
}
}
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
console.log(uf.find(0) === uf.find(2));Radix Sort is a non-comparison sorting algorithm that sorts integers digit by digit from least significant to most significant.
It uses Counting Sort as a subroutine for each digit position.
Characteristics- Time Complexity O(d*(n+b))
- Stable sorting algorithm
- Works well for fixed-length integers
- Faster than comparison sorts for large n
function radixSort(arr) {
const max = Math.max(...arr);
let exp = 1;
while (Math.floor(max / exp) > 0) {
countingSortByDigit(arr, exp);
exp *= 10;
}
return arr;
}
function countingSortByDigit(arr, exp) {
const output = new Array(arr.length).fill(0);
const count = new Array(10).fill(0);
for (const num of arr) count[Math.floor(num / exp) % 10]++;
for (let i = 1; i < 10; i++) count[i] += count[i - 1];
for (let i = arr.length - 1; i >= 0; i--) {
const digit = Math.floor(arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
for (let i = 0; i < arr.length; i++) arr[i] = output[i];
}
console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));Bucket Sort distributes elements into a number of buckets, sorts each bucket individually, then concatenates them.
It is efficient when data is uniformly distributed over a range.
Characteristics- Average Time Complexity O(n+k)
- Best for uniformly distributed data
- Not in-place algorithm
- Stable when using stable sub-sort
function bucketSort(arr) {
const n = arr.length;
const buckets = Array.from({ length: n }, () => []);
for (const num of arr) {
const idx = Math.floor(num * n);
buckets[idx].push(num);
}
return buckets.flatMap(bucket => bucket.sort((a, b) => a - b));
}
console.log(bucketSort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12]));Shell Sort is an in-place comparison sort that generalizes insertion sort by allowing swaps of elements far apart.
It reduces the gap between compared elements progressively until it becomes 1, at which point it behaves like insertion sort.
Characteristics- Time Complexity depends on gap sequence
- Space Complexity O(1)
- In-place sorting
- Improvement over insertion sort
function shellSort(arr) {
let gap = Math.floor(arr.length / 2);
while (gap > 0) {
for (let i = gap; i < arr.length; i++) {
const temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
console.log(shellSort([64, 34, 25, 12, 22, 11, 90]));Interpolation Search is an improved version of binary search that works on uniformly distributed sorted arrays.
It uses the formula to estimate the position of the target element instead of always picking the middle.
Characteristics- Average Time Complexity O(log log n)
- Worst Case O(n)
- Works best on uniform data
- Faster than binary search for uniform distributions
function interpolationSearch(arr, target) {
let low = 0, high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
const pos = low + Math.floor(
((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
);
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
console.log(interpolationSearch([10, 20, 30, 40, 50], 30));Exponential Search finds the range where an element may be present and then applies binary search within that range.
It is especially useful when the array is unbounded or infinite.
Characteristics- Time Complexity O(log n)
- Works on sorted arrays
- Useful for unbounded arrays
- Combines linear and binary search
function exponentialSearch(arr, target) {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) i *= 2;
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 1));
}
function binarySearch(arr, target, left, right) {
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
console.log(exponentialSearch([1,2,3,4,5,6,7,8,9,10], 7));An N-ary Tree is a tree data structure where each node can have at most N children.
Unlike a binary tree limited to 2 children, N-ary trees are more flexible for hierarchical data.
Applications- File system directories
- Organization charts
- XML/HTML DOM parsing
- Game tree representations
class NaryNode {
constructor(data) {
this.data = data;
this.children = [];
}
}
const root = new NaryNode(1);
const child1 = new NaryNode(2);
const child2 = new NaryNode(3);
const child3 = new NaryNode(4);
root.children.push(child1, child2, child3);
console.log(root);A Red-Black Tree is a self-balancing BST where each node has a color (red or black) used to ensure balance.
It guarantees O(log n) time for search, insert, and delete operations in all cases.
Properties- Root is always black
- No two consecutive red nodes
- Equal black height on all paths
- Used in Java TreeMap and C++ std::map
class RBNode {
constructor(data, color = "RED") {
this.data = data;
this.color = color;
this.left = null;
this.right = null;
this.parent = null;
}
}
const root = new RBNode(10, "BLACK");
root.left = new RBNode(5);
root.right = new RBNode(20);
console.log(root);The Bellman-Ford Algorithm computes shortest paths from a source vertex to all other vertices, even with negative weight edges.
Unlike Dijkstra, it can detect negative weight cycles in a graph.
Properties- Time Complexity O(V*E)
- Handles negative weights
- Detects negative cycles
- Slower than Dijkstra
function bellmanFord(graph, vertices, edges, src) {
const dist = new Array(vertices).fill(Infinity);
dist[src] = 0;
for (let i = 1; i < vertices; i++) {
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
return dist;
}
const edges = [[0,1,4],[0,2,5],[1,2,-3],[2,3,2]];
console.log(bellmanFord({}, 4, edges, 0));Kruskal's Algorithm finds the Minimum Spanning Tree by sorting all edges by weight and adding them if they don't form a cycle.
It uses the Union-Find data structure for efficient cycle detection.
Properties- Works on sparse graphs
- Time Complexity O(E log E)
- Greedy algorithm
- Uses Union-Find internally
function kruskal(edges, n) {
edges.sort((a, b) => a[2] - b[2]);
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
parent[find(x)] = find(y);
}
let mstCost = 0;
const mstEdges = [];
for (const [u, v, w] of edges) {
if (find(u) !== find(v)) {
union(u, v);
mstCost += w;
mstEdges.push([u, v, w]);
}
}
return { mstCost, mstEdges };
}
const edges = [[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]];
console.log(kruskal(edges, 4));A Fenwick Tree is a data structure that efficiently supports prefix sum queries and point updates on an array.
It uses a binary representation trick to achieve O(log n) for both operations with less space than a segment tree.
Applications- Prefix sum queries
- Frequency counting
- Inversion count in array
- Competitive programming
class FenwickTree {
constructor(n) {
this.n = n;
this.tree = new Array(n + 1).fill(0);
}
update(i, delta) {
for (; i <= this.n; i += i & (-i))
this.tree[i] += delta;
}
query(i) {
let sum = 0;
for (; i > 0; i -= i & (-i))
sum += this.tree[i];
return sum;
}
}
const ft = new FenwickTree(8);
ft.update(1, 3);
ft.update(3, 2);
ft.update(5, 5);
console.log(ft.query(5));A Sparse Table is a data structure for answering range minimum (or maximum) queries in O(1) after O(n log n) preprocessing.
It exploits the idempotent property of the min/max operation for efficient lookups.
Properties- Query Time O(1)
- Build Time O(n log n)
- Space O(n log n)
- Immutable after construction
function buildSparseTable(arr) {
const n = arr.length;
const LOG = Math.floor(Math.log2(n)) + 1;
const table = Array.from({ length: n }, () => new Array(LOG).fill(0));
for (let i = 0; i < n; i++) table[i][0] = arr[i];
for (let j = 1; j < LOG; j++)
for (let i = 0; i + (1 << j) <= n; i++)
table[i][j] = Math.min(table[i][j-1], table[i + (1 << (j-1))][j-1]);
return table;
}
function queryMin(table, l, r) {
const k = Math.floor(Math.log2(r - l + 1));
return Math.min(table[l][k], table[r - (1 << k) + 1][k]);
}
const arr = [2, 4, 3, 1, 6, 7, 8, 9];
const table = buildSparseTable(arr);
console.log(queryMin(table, 0, 4));The Z Algorithm computes for each position in a string the length of the longest substring starting from that position that is also a prefix of the string.
It is used for efficient pattern matching in O(n+m) time.
Applications- Pattern searching
- String matching
- Finding all occurrences of a pattern
- Longest palindromic prefix
function zAlgorithm(s) {
const z = new Array(s.length).fill(0);
z[0] = s.length;
let l = 0, r = 0;
for (let i = 1; i < s.length; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < s.length && s[z[i]] === s[i + z[i]]) z[i]++;
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z;
}
console.log(zAlgorithm("aabxaa"));The KMP (Knuth-Morris-Pratt) Algorithm searches for a pattern in a text using a failure function to skip unnecessary comparisons.
It achieves O(n+m) time complexity by avoiding re-examination of already matched characters.
Properties- Time Complexity O(n+m)
- No backtracking in text
- Uses LPS (Longest Prefix Suffix) array
- Efficient for repeated patterns
function kmpSearch(text, pattern) {
const lps = buildLPS(pattern);
const result = [];
let j = 0;
for (let i = 0; i < text.length; ) {
if (text[i] === pattern[j]) { i++; j++; }
if (j === pattern.length) { result.push(i - j); j = lps[j - 1]; }
else if (i < text.length && text[i] !== pattern[j]) {
if (j !== 0) j = lps[j - 1];
else i++;
}
}
return result;
}
function buildLPS(pattern) {
const lps = new Array(pattern.length).fill(0);
let len = 0, i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[len]) { lps[i++] = ++len; }
else if (len !== 0) len = lps[len - 1];
else lps[i++] = 0;
}
return lps;
}
console.log(kmpSearch("AABAACAADAABAABA", "AABA"));The Rabin-Karp Algorithm uses hashing to find pattern occurrences in a text efficiently.
It computes a rolling hash for each window of text and compares with the pattern hash.
Properties- Average Time Complexity O(n+m)
- Worst Case O(n*m)
- Uses rolling hash technique
- Useful for multiple pattern search
function rabinKarp(text, pattern) {
const d = 256, q = 101;
const n = text.length, m = pattern.length;
let h = 1, pHash = 0, tHash = 0;
const result = [];
for (let i = 0; i < m - 1; i++) h = (h * d) % q;
for (let i = 0; i < m; i++) {
pHash = (d * pHash + pattern.charCodeAt(i)) % q;
tHash = (d * tHash + text.charCodeAt(i)) % q;
}
for (let i = 0; i <= n - m; i++) {
if (pHash === tHash && text.slice(i, i + m) === pattern) result.push(i);
if (i < n - m) {
tHash = (d * (tHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
if (tHash < 0) tHash += q;
}
}
return result;
}
console.log(rabinKarp("GEEKS FOR GEEKS", "GEEK"));Level Order Traversal visits all nodes of a tree level by level from top to bottom, left to right.
It is implemented using a queue and is essentially BFS applied to trees.
Applications- Finding shortest path in unweighted trees
- Printing tree level by level
- Connecting nodes at same level
- Zigzag traversal variant
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const level = [];
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.data);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
const root = { data:1, left:{ data:2, left:{ data:4, left:null, right:null }, right:{ data:5, left:null, right:null } }, right:{ data:3, left:null, right:null } };
console.log(levelOrder(root));Zigzag Traversal visits tree nodes level by level but alternates the direction at each level.
Odd levels go left to right, even levels go right to left, creating a zigzag pattern.
Approach- Uses a queue for BFS
- Tracks direction with a boolean flag
- Fills level array from either end
- Time Complexity O(n)
function zigzagTraversal(root) {
if (!root) return [];
const result = [];
const queue = [root];
let leftToRight = true;
while (queue.length) {
const size = queue.length;
const level = new Array(size);
for (let i = 0; i < size; i++) {
const node = queue.shift();
const idx = leftToRight ? i : size - 1 - i;
level[idx] = node.data;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
leftToRight = !leftToRight;
}
return result;
}
const root = { data:1, left:{ data:2, left:{ data:4, left:null, right:null }, right:{ data:5, left:null, right:null } }, right:{ data:3, left:null, right:null } };
console.log(zigzagTraversal(root));Memoization is a top-down dynamic programming technique that caches results of expensive function calls.
When the same inputs occur again, the cached result is returned instead of recomputing.
Benefits- Avoids redundant computation
- Improves recursive algorithm performance
- Easy to implement with maps
- Converts exponential to polynomial time
function memoize(fn) {
const cache = {};
return function(...args) {
const key = JSON.stringify(args);
if (key in cache) return cache[key];
return (cache[key] = fn.apply(this, args));
};
}
const slowSquare = (n) => n * n;
const fastSquare = memoize(slowSquare);
console.log(fastSquare(5));
console.log(fastSquare(5));Tabulation is a bottom-up dynamic programming approach that fills a table iteratively starting from the smallest subproblems.
It avoids recursion overhead and is generally more space efficient than memoization.
Advantages- No recursion stack overhead
- Iterative and predictable
- Easier to optimize space
- Better cache performance
function fibTabulation(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(fibTabulation(10));The Coin Change Problem finds the minimum number of coins needed to make a given amount using available denominations.
It is a classic dynamic programming problem demonstrating optimal substructure.
Approach- Uses bottom-up DP table
- Time Complexity O(n*amount)
- Space Complexity O(amount)
- Returns -1 if no solution exists
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 5, 6, 9], 11));The Longest Increasing Subsequence (LIS) finds the length of the longest subsequence of a given array in which all elements are in strictly increasing order.
It is a fundamental dynamic programming problem with applications in various domains.
Approach- DP approach: O(n²)
- Binary search approach: O(n log n)
- Classic interview problem
- Used in patience sorting
function lis(arr) {
const dp = new Array(arr.length).fill(1);
for (let i = 1; i < arr.length; i++) {
for (let j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
console.log(lis([10, 9, 2, 5, 3, 7, 101, 18]));Matrix Chain Multiplication finds the most efficient way to multiply a sequence of matrices to minimize total scalar multiplications.
The order of multiplication matters and the optimal order is found using dynamic programming.
Properties- Time Complexity O(n³)
- Space Complexity O(n²)
- Classic DP interval problem
- Does not actually multiply matrices
function matrixChain(dims) {
const n = dims.length - 1;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]);
}
}
}
return dp[0][n - 1];
}
console.log(matrixChain([10, 30, 5, 60]));Edit Distance (Levenshtein Distance) is the minimum number of operations (insert, delete, replace) needed to transform one string into another.
It is solved efficiently using a 2D dynamic programming table.
Applications- Spell checkers
- DNA sequence alignment
- Plagiarism detection
- Natural language processing
function editDistance(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({ length: m + 1 }, (_, i) =>
Array.from({ length: n + 1 }, (_, j) => i || j)
);
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
}
}
return dp[m][n];
}
console.log(editDistance("sunday", "saturday"));The Subset Sum Problem determines whether there exists a subset of the given array whose elements sum to a target value.
It is solved using dynamic programming with a 2D boolean table.
Properties- Time Complexity O(n*target)
- Space Complexity O(n*target)
- NP-Complete in general
- Solvable with DP for small targets
function subsetSum(arr, target) {
const n = arr.length;
const dp = Array.from({ length: n + 1 }, () => new Array(target + 1).fill(false));
for (let i = 0; i <= n; i++) dp[i][0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= target; j++) {
if (arr[i-1] <= j) dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i-1]];
else dp[i][j] = dp[i-1][j];
}
}
return dp[n][target];
}
console.log(subsetSum([3, 34, 4, 12, 5, 2], 9));The Word Break Problem checks if a string can be segmented into a sequence of words from a given dictionary.
It is solved using dynamic programming where dp[i] represents if the first i characters can be segmented.
Applications- Natural language processing
- Text segmentation
- Search engine keyword parsing
- Chinese word segmentation
function wordBreak(s, wordDict) {
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
const wordSet = new Set(wordDict);
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
}
console.log(wordBreak("leetcode", ["leet", "code"]));The House Robber Problem finds the maximum money that can be robbed from houses arranged in a line without robbing two adjacent houses.
It is a classic dynamic programming problem using only two previous states.
Approach- Time Complexity O(n)
- Space Complexity O(1) optimized
- At each house choose rob or skip
- dp[i] = max(dp[i-1], dp[i-2] + nums[i])
function rob(nums) {
if (nums.length === 1) return nums[0];
const dp = [nums[0], Math.max(nums[0], nums[1])];
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[nums.length - 1];
}
console.log(rob([2, 7, 9, 3, 1]));The Climbing Stairs Problem counts the number of distinct ways to reach the top of n stairs, taking 1 or 2 steps at a time.
The pattern follows the Fibonacci sequence and is a great introduction to dynamic programming.
Key Insight- f(n) = f(n-1) + f(n-2)
- Time Complexity O(n)
- Space Complexity O(1) optimized
- Same as Fibonacci pattern
function climbStairs(n) {
if (n <= 2) return n;
const dp = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
console.log(climbStairs(10));Reversing a Linked List involves changing the direction of all next pointers so the last node becomes the head.
This is done iteratively using three pointers: previous, current, and next.
Approach- Time Complexity O(n)
- Space Complexity O(1)
- Can also be done recursively
- Classic linked list interview question
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
const list = { data: 1, next: { data: 2, next: { data: 3, next: null } } };
console.log(reverseList(list));Cycle detection in a linked list uses Floyd's Cycle Detection Algorithm (Tortoise and Hare).
A slow pointer moves one step and a fast pointer moves two steps. If they meet, a cycle exists.
Properties- Time Complexity O(n)
- Space Complexity O(1)
- No extra memory needed
- Also finds cycle start point
function detectCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
console.log("Cycle detection using Floyd's algorithm");Merging two sorted linked lists produces a single sorted linked list by comparing nodes from both lists.
A dummy head node simplifies the merge logic by eliminating edge cases.
Approach- Time Complexity O(n+m)
- Space Complexity O(1)
- Iterative approach is preferred
- Can also be done recursively
function mergeLists(l1, l2) {
const dummy = { next: null };
let curr = dummy;
while (l1 && l2) {
if (l1.data <= l2.data) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}
const l1 = { data:1, next:{ data:3, next:{ data:5, next:null } } };
const l2 = { data:2, next:{ data:4, next:{ data:6, next:null } } };
let result = mergeLists(l1, l2);
while(result){ console.log(result.data); result = result.next; }Two strings are anagrams if they contain the same characters with the same frequencies, just in different orders.
We count character frequencies and compare them for both strings.
Approaches- Sort both strings and compare
- Use frequency count map
- Time Complexity O(n)
- Space Complexity O(1) for fixed alphabet
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = {};
for (const ch of s) count[ch] = (count[ch] || 0) + 1;
for (const ch of t) {
if (!count[ch]) return false;
count[ch]--;
}
return true;
}
console.log(isAnagram("anagram", "nagaram"));A palindrome reads the same forwards and backwards after ignoring non-alphanumeric characters and case.
We clean the string first, then compare it with its reverse.
Approaches- Reverse and compare
- Two pointer technique
- Time Complexity O(n)
- Space Complexity O(n)
function isPalindrome(s) {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
return cleaned === cleaned.split("").reverse().join("");
}
console.log(isPalindrome("A man, a plan, a canal: Panama"));Valid parentheses checking determines if every opening bracket has a corresponding closing bracket in the correct order.
A stack is used to push opening brackets and pop them when a matching closing bracket is found.
Approach- Use a stack
- Time Complexity O(n)
- Space Complexity O(n)
- Classic stack interview problem
function isValid(s) {
const stack = [];
const map = { ")": "(", "}": "{", "]": "[" };
for (const ch of s) {
if ("({[".includes(ch)) stack.push(ch);
else if (stack.pop() !== map[ch]) return false;
}
return stack.length === 0;
}
console.log(isValid("()[]{}}"));
console.log(isValid("()[]{}"));The maximum depth of a binary tree is the number of nodes along the longest path from root to the farthest leaf.
It is found recursively by taking the max of left and right subtree depths plus one.
Approach- Recursive DFS
- Iterative BFS level count
- Time Complexity O(n)
- Space Complexity O(h) where h is height
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
const root = { data:1, left:{ data:2, left:{ data:4, left:null, right:null }, right:null }, right:{ data:3, left:null, right:null } };
console.log(maxDepth(root));A binary tree is symmetric if its left and right subtrees are mirror images of each other.
We recursively check if left and right subtrees are mirrors by comparing corresponding nodes.
Approach- Recursive mirror check
- Iterative queue approach
- Time Complexity O(n)
- Space Complexity O(n)
function isSymmetric(root) {
function isMirror(left, right) {
if (!left && !right) return true;
if (!left || !right) return false;
return left.data === right.data &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left);
}
return isMirror(root.left, root.right);
}
const root = { data:1, left:{ data:2, left:{ data:3, left:null, right:null }, right:{ data:4, left:null, right:null } }, right:{ data:2, left:{ data:4, left:null, right:null }, right:{ data:3, left:null, right:null } } };
console.log(isSymmetric(root));The Lowest Common Ancestor (LCA) of two nodes p and q in a binary tree is the deepest node that has both p and q as descendants.
It is found using a recursive approach that propagates node information up the tree.
Approach- Recursive post-order traversal
- Time Complexity O(n)
- Space Complexity O(h)
- Used in range queries and tree problems
function lca(root, p, q) {
if (!root || root.data === p || root.data === q) return root;
const left = lca(root.left, p, q);
const right = lca(root.right, p, q);
return left && right ? root : left || right;
}
const root = { data:3, left:{ data:5, left:{ data:6, left:null, right:null }, right:{ data:2, left:null, right:null } }, right:{ data:1, left:null, right:null } };
console.log(lca(root, 5, 1).data);Spiral Order Traversal visits matrix elements layer by layer in a clockwise spiral direction.
It uses four boundary pointers (top, bottom, left, right) that shrink after each direction pass.
Approach- Four boundary variables
- Time Complexity O(m*n)
- Space Complexity O(1)
- Classic matrix interview problem
function spiralOrder(matrix) {
const result = [];
let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let i = left; i <= right; i++) result.push(matrix[top][i]);
top++;
for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
right--;
if (top <= bottom) { for (let i = right; i >= left; i--) result.push(matrix[bottom][i]); bottom--; }
if (left <= right) { for (let i = bottom; i >= top; i--) result.push(matrix[i][left]); left++; }
}
return result;
}
const matrix = [[1,2,3],[4,5,6],[7,8,9]];
console.log(spiralOrder(matrix));Rotating a matrix 90 degrees clockwise can be done in-place by first transposing the matrix and then reversing each row.
This avoids using extra space and achieves the transformation in O(n²) time.
Steps- Step 1: Transpose the matrix
- Step 2: Reverse each row
- Time Complexity O(n²)
- Space Complexity O(1)
function rotate(matrix) {
const n = matrix.length;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
for (let i = 0; i < n; i++)
matrix[i].reverse();
return matrix;
}
console.log(rotate([[1,2,3],[4,5,6],[7,8,9]]));Flood Fill Algorithm fills a connected region of the same color with a new color, starting from a seed point.
It is the algorithm behind the paint bucket tool in image editing software.
Applications- Paint bucket in image editors
- Solving maze problems
- Finding connected components
- Game map region filling
function floodFill(image, sr, sc, color) {
const origColor = image[sr][sc];
if (origColor === color) return image;
function fill(r, c) {
if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
if (image[r][c] !== origColor) return;
image[r][c] = color;
fill(r+1, c); fill(r-1, c); fill(r, c+1); fill(r, c-1);
}
fill(sr, sc);
return image;
}
console.log(floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2));The Number of Islands problem counts the number of connected groups of '1's (land) in a 2D grid surrounded by '0's (water).
It uses DFS to mark all connected land cells as visited when a new island is discovered.
Approach- DFS or BFS on grid
- Time Complexity O(m*n)
- Space Complexity O(m*n)
- Classic graph traversal problem
function numIslands(grid) {
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] === "0") return;
grid[r][c] = "0";
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
}
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === "1") { count++; dfs(r, c); }
}
}
return count;
}
console.log(numIslands([["1","1","0"],["0","1","0"],["0","0","1"]]));A Power Set is the set of all possible subsets of a given set, including the empty set and the set itself.
A set with n elements has 2ⁿ subsets in its power set.
Approach- Iterative approach using bit manipulation
- Recursive backtracking
- Time Complexity O(2ⁿ)
- Space Complexity O(2ⁿ)
function powerSet(nums) {
const result = [[]];
for (const num of nums) {
const len = result.length;
for (let i = 0; i < len; i++) {
result.push([...result[i], num]);
}
}
return result;
}
console.log(powerSet([1, 2, 3]));A Permutation is an arrangement of all elements of a set in every possible order.
For n elements, there are n! possible permutations and they are generated using backtracking.
Approach- Backtracking with recursion
- Time Complexity O(n*n!)
- Space Complexity O(n)
- Classic backtracking problem
function permute(nums) {
const result = [];
function backtrack(current, remaining) {
if (remaining.length === 0) { result.push(current); return; }
for (let i = 0; i < remaining.length; i++) {
backtrack(
[...current, remaining[i]],
[...remaining.slice(0, i), ...remaining.slice(i + 1)]
);
}
}
backtrack([], nums);
return result;
}
console.log(permute([1, 2, 3]));The N-Queens Problem places N queens on an N×N chessboard such that no two queens attack each other.
It is solved using backtracking, placing queens row by row and checking column and diagonal conflicts.
Approach- Backtracking
- Track columns and diagonals
- Time Complexity O(n!)
- Classic constraint satisfaction problem
function solveNQueens(n) {
const result = [];
function backtrack(row, cols, diag1, diag2, board) {
if (row === n) { result.push(board.map(r => r.join(""))); return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
board[row][col] = "Q";
cols.add(col); diag1.add(row - col); diag2.add(row + col);
backtrack(row + 1, cols, diag1, diag2, board);
board[row][col] = ".";
cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
}
}
backtrack(0, new Set(), new Set(), new Set(), Array.from({ length: n }, () => new Array(n).fill(".")));
return result;
}
console.log(solveNQueens(4).length);A Sudoku Solver fills empty cells in a 9×9 grid with digits 1–9 so that each row, column, and 3×3 box contains all digits exactly once.
It uses backtracking to try each valid digit and backtracks when a conflict is detected.
Approach- Backtracking recursion
- Validates row, column, and box
- Tries digits 1 to 9
- Classic constraint satisfaction
function solveSudoku(board) {
function isValid(board, row, col, num) {
const box_row = Math.floor(row / 3) * 3;
const box_col = Math.floor(col / 3) * 3;
for (let i = 0; i < 9; i++) {
if (board[row][i] === num) return false;
if (board[i][col] === num) return false;
if (board[box_row + Math.floor(i / 3)][box_col + i % 3] === num) return false;
}
return true;
}
function solve(board) {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] === ".") {
for (let num = 1; num <= 9; num++) {
const ch = String(num);
if (isValid(board, r, c, ch)) {
board[r][c] = ch;
if (solve(board)) return true;
board[r][c] = ".";
}
}
return false;
}
}
}
return true;
}
solve(board);
return board;
}
console.log("Sudoku solver implemented with backtracking");Generating all valid parentheses combinations of n pairs uses backtracking by tracking the count of open and close brackets placed so far.
A close bracket can only be added if there are more open brackets currently than close brackets.
Approach- Backtracking recursion
- Time Complexity O(4ⁿ/√n)
- Generates Catalan number count of results
- Classic backtracking problem
function generateParentheses(n) {
const result = [];
function backtrack(s, open, close) {
if (s.length === 2 * n) { result.push(s); return; }
if (open < n) backtrack(s + "(", open + 1, close);
if (close < open) backtrack(s + ")", open, close + 1);
}
backtrack("", 0, 0);
return result;
}
console.log(generateParentheses(3));The Two Sum Problem finds two numbers in an array that add up to a given target and returns their indices.
Using a HashMap, it achieves O(n) time by storing complement values as we iterate.
Approaches- Brute force O(n²)
- HashMap approach O(n)
- Two pointer on sorted array O(n log n)
- Most common first interview question
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) return [map.get(complement), i];
map.set(nums[i], i);
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9));The Three Sum Problem finds all unique triplets in an array that sum to zero.
By sorting the array first and using two pointers for the remaining pair, it achieves O(n²) time.
Approach- Sort array first
- Fix one element, two pointer for rest
- Time Complexity O(n²)
- Handle duplicates carefully
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i-1]) continue;
let left = i + 1, right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left+1]) left++;
while (left < right && nums[right] === nums[right-1]) right--;
left++; right--;
} else if (sum < 0) left++;
else right--;
}
}
return result;
}
console.log(threeSum([-1, 0, 1, 2, -1, -4]));The Majority Element Problem finds the element that appears more than n/2 times in an array of n elements.
Boyer-Moore Voting Algorithm solves this in O(n) time and O(1) space by maintaining a candidate and count.
Properties- Time Complexity O(n)
- Space Complexity O(1)
- Boyer-Moore Voting Algorithm
- Majority element always exists in valid input
function majorityElement(nums) {
let count = 0, candidate = null;
for (const num of nums) {
if (count === 0) candidate = num;
count += num === candidate ? 1 : -1;
}
return candidate;
}
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]));The Trapping Rain Water Problem calculates how much water can be trapped between elevation bars after it rains.
The two-pointer approach solves it in O(n) time and O(1) space by tracking max heights from both ends.
Approach- Two pointer technique
- Time Complexity O(n)
- Space Complexity O(1)
- Also solvable with prefix/suffix max arrays
function trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) leftMax = height[left];
else water += leftMax - height[left];
left++;
} else {
if (height[right] >= rightMax) rightMax = height[right];
else water += rightMax - height[right];
right--;
}
}
return water;
}
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));The Sliding Window Maximum Problem finds the maximum element in every window of size k as it slides through the array.
A Deque (monotonic queue) maintains indices in decreasing order of their values for O(n) solution.
Approach- Monotonic deque
- Time Complexity O(n)
- Space Complexity O(k)
- Classic deque application
function maxSlidingWindow(nums, k) {
const result = [];
const deque = [];
for (let i = 0; i < nums.length; i++) {
while (deque.length && deque[0] < i - k + 1) deque.shift();
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
deque.push(i);
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
}
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));This problem finds the length of the longest substring that contains no repeating characters.
The sliding window with a HashMap approach tracks character positions to efficiently skip past duplicates.
Approach- Sliding window with HashMap
- Time Complexity O(n)
- Space Complexity O(min(n, alphabet))
- Very common interview question
function lengthOfLongestSubstring(s) {
const map = new Map();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
if (map.has(s[right]) && map.get(s[right]) >= left) {
left = map.get(s[right]) + 1;
}
map.set(s[right], right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
console.log(lengthOfLongestSubstring("abcabcbb"));The Container With Most Water Problem finds two lines from a given height array that together with the x-axis form a container holding the most water.
The two pointer approach moves the pointer with the shorter height inward to potentially find a taller pair.
Approach- Two pointer technique
- Time Complexity O(n)
- Space Complexity O(1)
- Greedy shrinking strategy
function maxArea(height) {
let left = 0, right = height.length - 1, max = 0;
while (left < right) {
max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
if (height[left] < height[right]) left++;
else right--;
}
return max;
}
console.log(maxArea([1,8,6,2,5,4,8,3,7]));A Min Stack is a stack data structure that supports push, pop, top, and retrieving the minimum element in O(1) time.
It uses an auxiliary stack that tracks the current minimum at every level of the main stack.
Operations- push() in O(1)
- pop() in O(1)
- top() in O(1)
- getMin() in O(1)
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(val) {
this.stack.push(val);
const min = this.minStack.length === 0 ? val : Math.min(val, this.minStack[this.minStack.length - 1]);
this.minStack.push(min);
}
pop() {
this.stack.pop();
this.minStack.pop();
}
top() { return this.stack[this.stack.length - 1]; }
getMin() { return this.minStack[this.minStack.length - 1]; }
}
const ms = new MinStack();
ms.push(-2); ms.push(0); ms.push(-3);
console.log(ms.getMin());
ms.pop();
console.log(ms.top());
console.log(ms.getMin());