coding-interview-university
A complete computer science study plan to become a software engineer.
- 364k
- CC-BY-SA-4.0
- 11 d ago
Data Structures and Algorithms in JavaScript
Repo learning-zone/javascript-data-structure, read from GitHub 1 min ago. learning-zone has not joined Take My Repo.
learning-zone/javascript-data-structure is a public repo on GitHub by learning-zone. Data Structures and Algorithms in JavaScript. It declares the MIT license on GitHub. It has 30 stars and last changed on 2026-04-21. Nobody has reviewed it on Take My Repo yet, which says nothing about its quality. Read from GitHub on 2026-11-18.
In the maintainer's words. Shown from GitHub; Take My Repo does not keep a copy.
Click ★ if you like the project. Your contributions are heartily ♡ welcome.
Complexity analysis measures how an algorithm's resource usage (time or memory) grows relative to the input size n. Big O notation describes the upper bound (worst case) of this growth, ignoring constants and lower-order terms.
Common use cases / why it matters:
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access arr[0] |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Single loop through array |
| O(n log n) | Linearithmic | Merge sort, Quick sort (avg) |
| O(n²) | Quadratic | Nested loops, Bubble sort |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci |
// O(1) — constant time function getFirst(arr) { return arr[0]; } // O(n) — linear time function sumArray(arr) { let total = 0; for (const x of arr) total += x; return total; } // O(n²) — quadratic (nested loops) function printPairs(arr) { for (let i = 0; i < arr.length; i++) for (let j = 0; j < arr.length; j++) console.log(arr[i], arr[j]); } // O(log n) — logarithmic (binary search) function bsExample(arr, target) { let lo = 0, hi = arr.length - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (arr[mid] === target) return mid; arr[mid] < target ? lo = mid + 1 : hi = mid - 1; } return -1; }
// O(n²) — naive: compare every pair function hasDuplicateSlow(arr) { for (let i = 0; i < arr.length; i++) for (let j = i + 1; j < arr.length; j++) if (arr[i] === arr[j]) return true; return false; } // O(n) — optimized using a Set (time–space trade-off) function hasDuplicateFast(arr) { const seen = new Set(); for (const val of arr) { if (seen.has(val)) return true; seen.add(val); } return false; } console.log(hasDuplicateFast([1, 2, 3, 2])); // true
Reduced O(n²) → O(n) by spending O(n) extra space.
// O(n) extra space — creates a new array function reverseWithExtraSpace(arr) { return arr.slice().reverse(); } // O(1) extra space — modifies array in place function reverseInPlace(arr) { let lo = 0, hi = arr.length - 1; while (lo < hi) { [arr[lo], arr[hi]] = [arr[hi], arr[lo]]; lo++; hi--; } return arr; } console.log(reverseInPlace([1, 2, 3, 4, 5])); // [5, 4, 3, 2, 1]
Both run in O(n) time.
reverseInPlaceuses O(1) space — preferred for large inputs.
| Algorithm | Best | Average | Worst | Notes |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | Target at start / not found |
| Binary Search | O(1) | O(log n) | O(log n) | Requires sorted array |
| Bubble Sort | O(n) | O(n²) | O(n²) | Best when already sorted |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | Worst: sorted array + bad pivot |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Consistent; costs O(n) space |
An array is a contiguous, ordered collection of elements stored at indexed positions. In JavaScript, arrays are dynamic — they can grow/shrink and hold mixed types.
Common use cases:
Math.max?function findMax(arr) { let max = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] > max) max = arr[i]; } return max; } console.log(findMax([3, 7, 1, 9, 4])); // 9
const arr = [1, 2, 2, 3, 4, 4, 5]; // Using Set const unique = [...new Set(arr)]; console.log(unique); // [1, 2, 3, 4, 5] // Using filter const unique2 = arr.filter((val, idx) => arr.indexOf(val) === idx); console.log(unique2); // [1, 2, 3, 4, 5]
k steps?function rotateRight(arr, k) { const n = arr.length; k = k % n; return [...arr.slice(n - k), ...arr.slice(0, n - k)]; } console.log(rotateRight([1, 2, 3, 4, 5], 2)); // [4, 5, 1, 2, 3]
function twoSum(arr, target) { const map = new Map(); for (let i = 0; i < arr.length; i++) { const complement = target - arr[i]; if (map.has(complement)) { return [map.get(complement), i]; } map.set(arr[i], i); } return []; } console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
function secondLargest(arr) { let first = -Infinity, second = -Infinity; for (const num of arr) { if (num > first) { second = first; first = num; } else if (num > second && num !== first) { second = num; } } return second === -Infinity ? null : second; } console.log(secondLargest([3, 7, 1, 9, 4])); // 7 console.log(secondLargest([5, 5, 5])); // null
Time: O(n) | Space: O(1) — single pass, no sorting needed.
function maxSubarraySum(arr) { let maxSum = arr[0], 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(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 [4,-1,2,1] console.log(maxSubarraySum([-1, -2, -3])); // -1
Time: O(n) | Space: O(1)
function buildPrefixSum(arr) { const prefix = [arr[0]]; for (let i = 1; i < arr.length; i++) prefix[i] = prefix[i - 1] + arr[i]; return prefix; } // Range sum in O(1) after O(n) preprocessing function rangeSum(prefix, l, r) { return l === 0 ? prefix[r] : prefix[r] - prefix[l - 1]; } const arr = [1, 2, 3, 4, 5]; const prefix = buildPrefixSum(arr); // [1, 3, 6, 10, 15] console.log(rangeSum(prefix, 1, 3)); // 9 (2+3+4) console.log(rangeSum(prefix, 0, 4)); // 15 (sum of all)
function mergeSorted(a, b) { const result = []; let i = 0, j = 0; while (i < a.length && j < b.length) { result.push(a[i] <= b[j] ? a[i++] : b[j++]); } return [...result, ...a.slice(i), ...b.slice(j)]; } console.log(mergeSorted([1, 3, 5], [2, 4, 6])); // [1, 2, 3, 4, 5, 6]
Time: O(m + n) | Space: O(m + n)
A string is an immutable sequence of characters. In JavaScript, strings are primitives but have array-like properties (indexable, iterable).
Common use cases:
// Method 1: Built-in split/reverse/join const reverse1 = str => str.split('').reverse().join(''); // Method 2: Loop function reverse2(str) { let result = ''; for (let i = str.length - 1; i >= 0; i--) result += str[i]; return result; } // Method 3: Two pointers function reverse3(str) { const arr = str.split(''); let lo = 0, hi = arr.length - 1; while (lo < hi) { [arr[lo], arr[hi]] = [arr[hi], arr[lo]]; lo++; hi--; } return arr.join(''); } console.log(reverse1('hello')); // 'olleh'
Time: O(n) | Space: O(n)
function isPalindrome(str) { // Normalize: lowercase, remove non-alphanumeric const s = str.toLowerCase().replace(/[^a-z0-9]/g, ''); let lo = 0, hi = s.length - 1; while (lo < hi) { if (s[lo] !== s[hi]) return false; lo++; hi--; } return true; } console.log(isPalindrome('racecar')); // true console.log(isPalindrome('A man a plan a canal Panama')); // true console.log(isPalindrome('hello')); // false
Time: O(n) | Space: O(n) for normalized string
function isAnagram(s1, s2) { if (s1.length !== s2.length) return false; const map = new Map(); for (const ch of s1) map.set(ch, (map.get(ch) || 0) + 1); for (const ch of s2) { if (!map.get(ch)) return false; map.set(ch, map.get(ch) - 1); } return true; } console.log(isAnagram('listen', 'silent')); // true console.log(isAnagram('hello', 'world')); // false
Time: O(n) | Space: O(k) — k = number of unique characters. Alternative:
s1.split('').sort().join('') === s2.split('').sort().join('')— O(n log n)
function reverseWords(sentence) { return sentence.trim().split(/\s+/).reverse().join(' '); } console.log(reverseWords('Hello World from Node')); // 'Node from World Hello' console.log(reverseWords(' extra spaces ')); // 'spaces extra'
function charFrequency(str) { const freq = new Map(); for (const ch of str) freq.set(ch, (freq.get(ch) || 0) + 1); return freq; } const freq = charFrequency('banana'); console.log([...freq.entries()]); // [['b',1],['a',3],['n',2]]
Prefer
Mapover plain objects when keys are dynamic — avoids prototype pollution risk.
Sorting algorithms arrange elements in a specific order (ascending/descending). The choice of algorithm depends on input size, memory constraints, and whether the data is partially sorted.
Common use cases:
Address Calculation Sort uses a hash function to place each element into a bucket at an estimated sorted position, then applies insertion sort within each bucket.
function addressCalculationSort(arr) { const n = arr.length; const max = Math.max(...arr); const buckets = Array.from({ length: n }, () => []); for (const num of arr) { const idx = Math.min(Math.floor((num / (max + 1)) * n), n - 1); buckets[idx].push(num); } return buckets.flatMap(bucket => { // Insertion sort within each bucket for (let i = 1; i < bucket.length; i++) { const key = bucket[i]; let j = i - 1; while (j >= 0 && bucket[j] > key) { bucket[j + 1] = bucket[j]; j--; } bucket[j + 1] = key; } return bucket; }); } console.log(addressCalculationSort([20, 5, 15, 10, 25, 30])); // [5, 10, 15, 20, 25, 30]
Average O(n) when keys are uniformly distributed — degenerate to O(n²) for clustered data.
Binary Tree Sort inserts all elements into a BST then performs an inorder traversal to retrieve them in sorted order.
function binaryTreeSort(arr) { let root = null; for (const val of arr) root = bstInsertNode(root, val); const result = []; function inorder(node) { if (!node) return; inorder(node.left); result.push(node.val); inorder(node.right); } inorder(root); return result; } function bstInsertNode(root, val) { if (!root) return { val, left: null, right: null }; if (val < root.val) root.left = bstInsertNode(root.left, val); else root.right = bstInsertNode(root.right, val); return root; } console.log(binaryTreeSort([5, 3, 8, 1, 4, 7, 9])); // [1, 3, 4, 5, 7, 8, 9]
Time: O(n log n) avg (balanced BST), O(n²) worst (sorted input → skewed tree) | Space: O(n).
function bubbleSort(arr) { const n = arr.length; for (let i = 0; i < n - 1; i++) { for (let j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr; } console.log(bubbleSort([64, 34, 25, 12, 22])); // [12, 22, 25, 34, 64]
Time: O(n²) | Space: O(1)
Bucket Sort distributes elements into buckets, sorts each bucket independently, then concatenates.
function bucketSort(arr, bucketCount = 10) { if (arr.length === 0) return arr; const min = Math.min(...arr), max = Math.max(...arr); const range = (max - min) || 1; const buckets = Array.from({ length: bucketCount }, () => []); for (const num of arr) { const idx = Math.min( Math.floor(((num - min) / range) * bucketCount), bucketCount - 1 ); buckets[idx].push(num); } return buckets.flatMap(bucket => bucket.sort((a, b) => a - b)); } console.log(bucketSort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51])); // [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52] console.log(bucketSort([34, 7, 23, 32, 5, 62])); // [5, 7, 23, 32, 34, 62]
Time: O(n + k) average | Space: O(n + k) | Best for uniformly distributed data.
function heapSort(arr) { const n = arr.length; // Build max-heap from bottom up for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i); // Extract max to end, restore heap for (let i = n - 1; i > 0; i--) { [arr[0], arr[i]] = [arr[i], arr[0]]; // move root (max) to sorted portion heapify(arr, i, 0); } return arr; } function heapify(arr, n, i) { let largest = i; const l = 2 * i + 1, 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])); // [5, 6, 7, 11, 12, 13]
Time: O(n log n) always | Space: O(1) | In-place but not stable.
function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { const 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])); // [5, 6, 11, 12, 13]
Time: O(n²) worst, O(n) best (nearly sorted input) | Space: O(1) Best choice for small or nearly-sorted arrays.
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) { const result = []; let i = 0, j = 0; while (i < left.length && j < right.length) { result.push(left[i] <= right[j] ? left[i++] : right[j++]); } return [...result, ...left.slice(i), ...right.slice(j)]; } console.log(mergeSort([38, 27, 43, 3, 9])); // [3, 9, 27, 38, 43]
Time: O(n log n) | Space: O(n)
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, 80, 30, 90, 40])); // [10, 30, 40, 80, 90]
Time: O(n log n) avg, O(n²) worst | Space: O(log n)
Radix Sort sorts integers digit by digit from least significant (LSD) to most significant (MSD), using a stable counting sort at each pass.
function radixSort(arr) { const max = Math.max(...arr); for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) { arr = countByDigit(arr, exp); } return arr; } function countByDigit(arr, exp) { const n = arr.length, output = new Array(n), count = new Array(10).fill(0); for (let i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++; for (let i = 1; i < 10; i++) count[i] += count[i - 1]; // prefix sums for (let i = n - 1; i >= 0; i--) { // right-to-left for stability const d = Math.floor(arr[i] / exp) % 10; output[--count[d]] = arr[i]; } return output; } console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66])); // [2, 24, 45, 66, 75, 90, 170, 802]
Time: O(d × (n + k)) — d = digits, k = 10 | Space: O(n + k) | Stable sort.
function selectionSort(arr) { const n = arr.length; for (let i = 0; i < n - 1; i++) { let minIdx = i; for (let j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } if (minIdx !== i) [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; } return arr; } console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]
Time: O(n²) always | Space: O(1) | Performs at most n-1 swaps (fewer than Bubble Sort).
Shell Sort is a generalized Insertion Sort that first sorts elements far apart using a decreasing gap sequence, improving to insertion sort (gap = 1) at the end.
function shellSort(arr) { const n = arr.length; let gap = Math.floor(n / 2); // Shell\'s gap sequence while (gap > 0) { for (let i = gap; i < n; 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([12, 34, 54, 2, 3])); // [2, 3, 12, 34, 54] console.log(shellSort([5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5]
Time: O(n log² n) with good gap sequence | Space: O(1) | Faster than Insertion Sort on medium arrays.
For large data:
✔ Merge Sort — O(n log n) guaranteed; stable; costs O(n) space
✔ Quick Sort — O(n log n) average; in-place (O(log n) space)
✘ Bubble / Selection / Insertion Sort — O(n²), too slow for large n
JavaScript\'s built-in Array.prototype.sort() uses TimSort
(hybrid of Merge Sort + Insertion Sort) — O(n log n).
Searching algorithms find the location of a target value within a data structure. The most common are linear search (works on any array) and binary search (requires a sorted array).
Common use cases:
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, 9, 7], 9)); // 2 console.log(linearSearch([4, 2, 9, 7], 5)); // -1
Use when the array is unsorted or small. Time: O(n) | Space: O(1)
function binarySearch(arr, target) { let lo = 0, hi = arr.length - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (arr[mid] === target) return mid; else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3 console.log(binarySearch([1, 3, 5, 7, 9, 11], 6)); // -1
Time: O(log n) | Requires sorted array
function binarySearchRecursive(arr, target, lo = 0, hi = arr.length - 1) { if (lo > hi) return -1; const mid = Math.floor((lo + hi) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, hi); return binarySearchRecursive(arr, target, lo, mid - 1); } console.log(binarySearchRecursive([1, 3, 5, 7, 9], 7)); // 3 console.log(binarySearchRecursive([1, 3, 5, 7, 9], 6)); // -1
## Q. How do you find the first and last occurrence of an element in a sorted array?Time: O(log n) | Space: O(log n) due to call stack (vs O(1) for iterative).
function firstOccurrence(arr, target) { let lo = 0, hi = arr.length - 1, result = -1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (arr[mid] === target) { result = mid; hi = mid - 1; } // keep going left else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return result; } function lastOccurrence(arr, target) { let lo = 0, hi = arr.length - 1, result = -1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (arr[mid] === target) { result = mid; lo = mid + 1; } // keep going right else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return result; } const arr = [1, 2, 2, 2, 3, 4, 5]; console.log(firstOccurrence(arr, 2)); // 1 console.log(lastOccurrence(arr, 2)); // 3
Both O(log n) — modified binary search that doesn't stop at first match.
Builds a sparse index table of key positions, uses the index to jump to the correct segment, then does sequential search within that segment.
function indexedSequentialSearch(arr, target, segmentSize = 3) { const n = arr.length; // Build index: store first key and starting position of each segment const index = []; for (let i = 0; i < n; i += segmentSize) { index.push({ key: arr[i], pos: i }); } // Find which segment might contain target let start = 0; for (let i = 0; i < index.length; i++) { if (index[i].key > target) { start = i > 0 ? index[i - 1].pos : 0; break; } if (i === index.length - 1) start = index[i].pos; } // Sequential search within segment const end = Math.min(start +
learning-zone/javascript-data-structure is a public repo on GitHub by learning-zone. Data Structures and Algorithms in JavaScript.
It declares the MIT license on GitHub.
Its maker has not tagged a system, so it is unknown here. Its README says what it needs.
Open "Take it" on its page: Take My Repo writes an install plan for your machine and hands it to your AI agent (Claude Code, Codex or Cursor), which asks you before each step. Take My Repo has not tested it on any machine.
Its last change on GitHub was on 2026-04-21. Take My Repo does not judge from that whether it is maintained.
Nobody has reviewed it on Take My Repo yet, which says nothing about its quality.
A complete computer science study plan to become a software engineer.
Collection of various algorithms in mathematics, machine learning, computer science, physics, etc implemented in C for educational purposes.
A privacy-first, open-source platform for knowledge management and collaboration. Download link: http://github.com/logseq/logseq/releases. roadmap: https://logseq.io/p/NX4mc_ggEV
📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
World's largest Contributor driven code dataset | Used in Quark Search Engine, @OpenGenus IQ, OpenGenus Visual Project
React Flow | Svelte Flow | Vue Flow - Powerful open source libraries for building node-based UIs with React (https://reactflow.dev), Svelte (https://svelteflow.dev) and Vue (https://vueflow.dev). Ready out-of-the-box and infinitely customizable.
This page is also available as structured data, with the same sources and dates.
/api/v1/resources/gh/learning-zone/javascript-data-structureTake My Repo has not tested this on your machine. Requirements come from the project's own documentation.