javascriptalgorithms
📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
Top Related Projects
Algorithms and Data Structures implemented in JavaScript for beginners, following best practices.
💯 Curated coding interview preparation materials for busy software engineers
Learn how to design largescale systems. Prep for the system design interview. Includes Anki flashcards.
Everything you need to know to get the job.
A complete computer science study plan to become a software engineer.
⚡️ Front End interview preparation materials for busy engineers
Quick Overview
The trekhleb/javascriptalgorithms repository is a comprehensive collection of JavaScript implementations of various algorithms and data structures. It serves as an educational resource for developers to learn about fundamental computer science concepts and their practical applications in JavaScript.
Pros
 Extensive coverage of algorithms and data structures
 Welldocumented code with explanations and complexity analysis
 Includes unit tests for each implementation
 Regularly maintained and updated
Cons
 May be overwhelming for beginners due to the large number of algorithms
 Some implementations might not be optimized for production use
 Lacks advanced or specialized algorithms in certain domains
 Limited explanations of theoretical concepts behind the algorithms
Code Examples
 Binary Search implementation:
function binarySearch(sortedArray, seekElement) {
let startIndex = 0;
let endIndex = sortedArray.length  1;
while (startIndex <= endIndex) {
const middleIndex = startIndex + Math.floor((endIndex  startIndex) / 2);
if (sortedArray[middleIndex] === seekElement) {
return middleIndex;
}
if (sortedArray[middleIndex] < seekElement) {
startIndex = middleIndex + 1;
} else {
endIndex = middleIndex  1;
}
}
return 1;
}
 Bubble Sort implementation:
function bubbleSort(originalArray) {
const array = [...originalArray];
for (let i = 1; i < array.length; i += 1) {
for (let j = 0; j < array.length  i; j += 1) {
if (array[j] > array[j + 1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]];
}
}
}
return array;
}
 Linked List implementation:
class LinkedListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
append(value) {
const newNode = new LinkedListNode(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
return this;
}
}
Getting Started
To use the algorithms and data structures in your project:

Clone the repository:
git clone https://github.com/trekhleb/javascriptalgorithms.git

Navigate to the desired algorithm or data structure in the
src
directory. 
Copy the implementation into your project or import it directly:
import { binarySearch } from './path/to/binarysearch'; const array = [1, 2, 3, 4, 5]; const result = binarySearch(array, 3); console.log(result); // Output: 2

Refer to the accompanying README files for usage instructions and complexity analysis.
Competitor Comparisons
Algorithms and Data Structures implemented in JavaScript for beginners, following best practices.
Pros of JavaScript
 More comprehensive coverage of algorithms and data structures
 Better organization with categorized folders for different types of algorithms
 Includes unit tests for most implementations, enhancing reliability
Cons of JavaScript
 Less detailed explanations and comments in the code
 Fewer languagespecific optimizations compared to javascriptalgorithms
 Some implementations may be less efficient or not follow best practices
Code Comparison
javascriptalgorithms (Binary Search):
function binarySearch(sortedArray, seekElement) {
let startIndex = 0;
let endIndex = sortedArray.length  1;
while (startIndex <= endIndex) {
const middleIndex = startIndex + Math.floor((endIndex  startIndex) / 2);
// ... (rest of the implementation)
}
return 1;
}
JavaScript (Binary Search):
function binarySearch(arr, x, low = 0, high = arr.length  1) {
if (high >= low) {
const mid = Math.floor((high + low) / 2);
if (arr[mid] === x) return mid;
if (arr[mid] > x) return binarySearch(arr, x, low, mid  1);
return binarySearch(arr, x, mid + 1, high);
}
return 1;
}
The JavaScript implementation uses recursion, while javascriptalgorithms uses an iterative approach. The latter provides more detailed comments and explanations within the code.
💯 Curated coding interview preparation materials for busy software engineers
Pros of techinterviewhandbook
 Broader scope, covering various aspects of tech interviews beyond algorithms
 Includes nontechnical interview preparation and career advice
 Provides curated lists of resources and study materials
Cons of techinterviewhandbook
 Less focused on indepth algorithm implementations
 May not provide as much handson coding practice
 JavaScriptspecific content is more limited
Code Comparison
techinterviewhandbook:
// Example of a coding question from the handbook
function reverseString(str) {
return str.split('').reverse().join('');
}
javascriptalgorithms:
// Example of a more detailed algorithm implementation
export default class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
}
The code comparison shows that javascriptalgorithms tends to provide more detailed implementations of data structures and algorithms, while techinterviewhandbook focuses on concise examples and explanations of common interview questions.
Learn how to design largescale systems. Prep for the system design interview. Includes Anki flashcards.
Pros of systemdesignprimer
 Comprehensive coverage of system design concepts and principles
 Includes realworld examples and case studies from largescale systems
 Provides visual aids and diagrams to illustrate complex concepts
Cons of systemdesignprimer
 Focuses primarily on highlevel system design, less on implementation details
 May be overwhelming for beginners due to the breadth of topics covered
 Less handson coding practice compared to javascriptalgorithms
Code Comparison
systemdesignprimer (Python):
class Store(object):
def __init__(self, id, name):
self.id = id
self.name = name
javascriptalgorithms (JavaScript):
class BinaryTreeNode {
constructor(value = null) {
this.left = null;
this.right = null;
this.value = value;
}
}
The code snippets demonstrate the difference in focus between the two repositories. systemdesignprimer provides examples of highlevel system components, while javascriptalgorithms offers implementations of specific data structures and algorithms.
Everything you need to know to get the job.
Pros of interviews
 Covers a broader range of topics, including system design and objectoriented design
 Includes solutions in multiple programming languages (Java, Python, C++, etc.)
 Provides more comprehensive explanations and resources for each topic
Cons of interviews
 Less focused on JavaScriptspecific implementations
 Not as frequently updated as javascriptalgorithms
 Repository structure is less organized, making it harder to navigate
Code Comparison
interviews (Java):
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
javascriptalgorithms (JavaScript):
export default function reverseLinkedList(linkedList) {
let currNode = linkedList.head;
let prevNode = null;
let nextNode = null;
while (currNode) {
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
linkedList.head = prevNode;
return linkedList;
}
Both repositories offer valuable resources for algorithm and data structure preparation. interviews provides a more comprehensive coverage of interview topics across multiple languages, while javascriptalgorithms focuses specifically on JavaScript implementations with a wellorganized structure.
A complete computer science study plan to become a software engineer.
Pros of codinginterviewuniversity
 Comprehensive coverage of computer science fundamentals
 Languageagnostic approach, suitable for various programming languages
 Includes study plans and learning resources beyond just algorithms
Cons of codinginterviewuniversity
 Less focused on practical implementation of algorithms
 May be overwhelming for beginners due to its extensive content
 Lacks specific code examples for immediate practice
Code Comparison
codinginterviewuniversity doesn't provide direct code examples, while javascriptalgorithms offers implementations. For instance, javascriptalgorithms includes:
function binarySearch(sortedArray, seekElement) {
let startIndex = 0;
let endIndex = sortedArray.length  1;
while (startIndex <= endIndex) {
const middleIndex = startIndex + Math.floor((endIndex  startIndex) / 2);
// ... (implementation continues)
}
}
codinginterviewuniversity would typically link to external resources or provide pseudocode explanations instead of direct implementations.
Summary
javascriptalgorithms focuses on practical JavaScript implementations of algorithms and data structures, making it ideal for handson learners and those specifically interested in JavaScript. codinginterviewuniversity offers a broader, languageagnostic approach to computer science fundamentals and interview preparation, suitable for those seeking a comprehensive understanding across multiple topics. The choice between the two depends on the learner's goals, preferred learning style, and specific language interests.
⚡️ Front End interview preparation materials for busy engineers
Pros of Frontend Interview Handbook
 Focuses specifically on frontend development topics, making it more targeted for web developers
 Includes a wider range of interviewrelated content, such as behavioral questions and resume tips
 Offers content in multiple languages, making it accessible to a broader audience
Cons of Frontend Interview Handbook
 Less emphasis on indepth algorithm implementations and explanations
 May not be as useful for developers looking to improve their general programming skills beyond frontend development
Code Comparison
Frontend Interview Handbook (HTML example):
<button onclick="alert('Hello, World!')">Click me</button>
JavaScript Algorithms (Algorithm example):
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]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
The code comparison highlights the different focus areas of each repository. Frontend Interview Handbook provides examples related to web development, while JavaScript Algorithms offers implementations of various algorithms and data structures.
Convert designs to code with AI
Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.
Try Visual CopilotREADME
JavaScript Algorithms and Data Structures
ðºð¦ UKRAINE IS BEING ATTACKED BY RUSSIAN ARMY. CIVILIANS ARE GETTING KILLED. RESIDENTIAL AREAS ARE GETTING BOMBED.
 Help Ukraine via:
 More info on war.ukraine.ua and MFA of Ukraine
This repository contains JavaScript based examples of many popular algorithms and data structures.
Each algorithm and data structure has its own separate README with related explanations and links for further reading (including ones to YouTube videos).
Read this in other languages: ç®ä½ä¸æ, ç¹é«ä¸æ, íêµì´, æ¥æ¬èª, Polski, FranÃ§ais, EspaÃ±ol, PortuguÃªs, Ð ÑÑÑÐºÐ¸Ð¹, TÃ¼rkÃ§e, Italiana, Bahasa Indonesia, Ð£ÐºÑÐ°ÑÐ½ÑÑÐºÐ°, Arabic, Tiáº¿ng Viá»t, Deutsch, Uzbek
â Note that this project is meant to be used for learning and researching purposes only, and it is not meant to be used for production.
Data Structures
A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
Remember that each data has its own tradeoffs. And you need to pay attention more to why you're choosing a certain data structure than to how to implement it.
B
 Beginner, A
 Advanced
B
Linked ListB
Doubly Linked ListB
QueueB
StackB
Hash TableB
Heap  max and min heap versionsB
Priority QueueA
TrieA
TreeA
Binary Search TreeA
AVL TreeA
RedBlack TreeA
Segment Tree  with min/max/sum range queries examplesA
Fenwick Tree (Binary Indexed Tree)
A
Graph (both directed and undirected)A
Disjoint Set  a unionâfind data structure or mergeâfind setA
Bloom FilterA
LRU Cache  Least Recently Used (LRU) cache
Algorithms
An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.
B
 Beginner, A
 Advanced
Algorithms by Topic
 Math
B
Bit Manipulation  set/get/update/clear bits, multiplication/division by two, make negative etc.B
Binary Floating Point  binary representation of the floatingpoint numbers.B
FactorialB
Fibonacci Number  classic and closedform versionsB
Prime Factors  finding prime factors and counting them using HardyRamanujan's theoremB
Primality Test (trial division method)B
Euclidean Algorithm  calculate the Greatest Common Divisor (GCD)B
Least Common Multiple (LCM)B
Sieve of Eratosthenes  finding all prime numbers up to any given limitB
Is Power of Two  check if the number is power of two (naive and bitwise algorithms)B
Pascal's TriangleB
Complex Number  complex numbers and basic operations with themB
Radian & Degree  radians to degree and backwards conversionB
Fast PoweringB
Horner's method  polynomial evaluationB
Matrices  matrices and basic matrix operations (multiplication, transposition, etc.)B
Euclidean Distance  distance between two points/vectors/matricesA
Integer PartitionA
Square Root  Newton's methodA
Liu Hui Ï Algorithm  approximate Ï calculations based on NgonsA
Discrete Fourier Transform  decompose a function of time (a signal) into the frequencies that make it up
 Sets
B
Cartesian Product  product of multiple setsB
FisherâYates Shuffle  random permutation of a finite sequenceA
Power Set  all subsets of a set (bitwise, backtracking, and cascading solutions)A
Permutations (with and without repetitions)A
Combinations (with and without repetitions)A
Longest Common Subsequence (LCS)A
Longest Increasing SubsequenceA
Shortest Common Supersequence (SCS)A
Knapsack Problem  "0/1" and "Unbound" onesA
Maximum Subarray  "Brute Force" and "Dynamic Programming" (Kadane's) versionsA
Combination Sum  find all combinations that form specific sum
 Strings
B
Hamming Distance  number of positions at which the symbols are differentB
Palindrome  check if the string is the same in reverseA
Levenshtein Distance  minimum edit distance between two sequencesA
KnuthâMorrisâPratt Algorithm (KMP Algorithm)  substring search (pattern matching)A
Z Algorithm  substring search (pattern matching)A
Rabin Karp Algorithm  substring searchA
Longest Common SubstringA
Regular Expression Matching
 Searches
B
Linear SearchB
Jump Search (or Block Search)  search in sorted arrayB
Binary Search  search in sorted arrayB
Interpolation Search  search in uniformly distributed sorted array
 Sorting
B
Bubble SortB
Selection SortB
Insertion SortB
Heap SortB
Merge SortB
Quicksort  inplace and noninplace implementationsB
ShellsortB
Counting SortB
Radix SortB
Bucket Sort
 Linked Lists
 Trees
B
DepthFirst Search (DFS)B
BreadthFirst Search (BFS)
 Graphs
B
DepthFirst Search (DFS)B
BreadthFirst Search (BFS)B
Kruskalâs Algorithm  finding Minimum Spanning Tree (MST) for weighted undirected graphA
Dijkstra Algorithm  finding the shortest paths to all graph vertices from single vertexA
BellmanFord Algorithm  finding the shortest paths to all graph vertices from single vertexA
FloydWarshall Algorithm  find the shortest paths between all pairs of verticesA
Detect Cycle  for both directed and undirected graphs (DFS and Disjoint Set based versions)A
Primâs Algorithm  finding Minimum Spanning Tree (MST) for weighted undirected graphA
Topological Sorting  DFS methodA
Articulation Points  Tarjan's algorithm (DFS based)A
Bridges  DFS based algorithmA
Eulerian Path and Eulerian Circuit  Fleury's algorithm  Visit every edge exactly onceA
Hamiltonian Cycle  Visit every vertex exactly onceA
Strongly Connected Components  Kosaraju's algorithmA
Travelling Salesman Problem  shortest possible route that visits each city and returns to the origin city
 Cryptography
B
Polynomial Hash  rolling hash function based on polynomialB
Rail Fence Cipher  a transposition cipher algorithm for encoding messagesB
Caesar Cipher  simple substitution cipherB
Hill Cipher  substitution cipher based on linear algebra
 Machine Learning
B
NanoNeuron  7 simple JS functions that illustrate how machines can actually learn (forward/backward propagation)B
kNN  knearest neighbors classification algorithmB
kMeans  kMeans clustering algorithm
 Image Processing
B
Seam Carving  contentaware image resizing algorithm
 Statistics
B
Weighted Random  select the random item from the list based on items' weights
 Evolutionary algorithms
A
Genetic algorithm  example of how the genetic algorithm may be applied for training the selfparking cars
 Uncategorized
B
Tower of HanoiB
Square Matrix Rotation  inplace algorithmB
Jump Game  backtracking, dynamic programming (topdown + bottomup) and greedy examplesB
Unique Paths  backtracking, dynamic programming and Pascal's Triangle based examplesB
Rain Terraces  trapping rain water problem (dynamic programming and brute force versions)B
Recursive Staircase  count the number of ways to reach to the top (4 solutions)B
Best Time To Buy Sell Stocks  divide and conquer and onepass examplesA
NQueens ProblemA
Knight's Tour
Algorithms by Paradigm
An algorithmic paradigm is a generic method or approach which underlies the design of a class of algorithms. It is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.
 Brute Force  look at all the possibilities and selects the best solution
B
Linear SearchB
Rain Terraces  trapping rain water problemB
Recursive Staircase  count the number of ways to reach to the topA
Maximum SubarrayA
Travelling Salesman Problem  shortest possible route that visits each city and returns to the origin cityA
Discrete Fourier Transform  decompose a function of time (a signal) into the frequencies that make it up
 Greedy  choose the best option at the current time, without any consideration for the future
B
Jump GameA
Unbound Knapsack ProblemA
Dijkstra Algorithm  finding the shortest path to all graph verticesA
Primâs Algorithm  finding Minimum Spanning Tree (MST) for weighted undirected graphA
Kruskalâs Algorithm  finding Minimum Spanning Tree (MST) for weighted undirected graph
 Divide and Conquer  divide the problem into smaller parts and then solve those parts
B
Binary SearchB
Tower of HanoiB
Pascal's TriangleB
Euclidean Algorithm  calculate the Greatest Common Divisor (GCD)B
Merge SortB
QuicksortB
Tree DepthFirst Search (DFS)B
Graph DepthFirst Search (DFS)B
Matrices  generating and traversing the matrices of different shapesB
Jump GameB
Fast PoweringB
Best Time To Buy Sell Stocks  divide and conquer and onepass examplesA
Permutations (with and without repetitions)A
Combinations (with and without repetitions)A
Maximum Subarray
 Dynamic Programming  build up a solution using previously found subsolutions
B
Fibonacci NumberB
Jump GameB
Unique PathsB
Rain Terraces  trapping rain water problemB
Recursive Staircase  count the number of ways to reach to the topB
Seam Carving  contentaware image resizing algorithmA
Levenshtein Distance  minimum edit distance between two sequencesA
Longest Common Subsequence (LCS)A
Longest Common SubstringA
Longest Increasing SubsequenceA
Shortest Common SupersequenceA
0/1 Knapsack ProblemA
Integer PartitionA
Maximum SubarrayA
BellmanFord Algorithm  finding the shortest path to all graph verticesA
FloydWarshall Algorithm  find the shortest paths between all pairs of verticesA
Regular Expression Matching
 Backtracking  similarly to brute force, try to generate all possible solutions, but each time you generate next solution you test
if it satisfies all conditions, and only then continue generating subsequent solutions. Otherwise, backtrack, and go on a
different path of finding a solution. Normally the DFS traversal of statespace is being used.
B
Jump GameB
Unique PathsB
Power Set  all subsets of a setA
Hamiltonian Cycle  Visit every vertex exactly onceA
NQueens ProblemA
Knight's TourA
Combination Sum  find all combinations that form specific sum
 Branch & Bound  remember the lowestcost solution found at each stage of the backtracking search, and use the cost of the lowestcost solution found so far as a lower bound on the cost of a leastcost solution to the problem, in order to discard partial solutions with costs larger than the lowestcost solution found so far. Normally BFS traversal in combination with DFS traversal of statespace tree is being used.
How to use this repository
Install all dependencies
npm install
Run ESLint
You may want to run it to check code quality.
npm run lint
Run all tests
npm test
Run tests by name
npm test  'LinkedList'
Troubleshooting
If linting or testing is failing, try to delete the node_modules
folder and reinstall npm packages:
rm rf ./node_modules
npm i
Also make sure that you're using a correct Node version (>=16
). If you're using nvm for Node version management you may run nvm use
from the root folder of the project and the correct version will be picked up.
Playground
You may play with datastructures and algorithms in ./src/playground/playground.js
file and write
tests for it in ./src/playground/__test__/playground.test.js
.
Then just simply run the following command to test if your playground code works as expected:
npm test  'playground'
Useful Information
References
Big O Notation
Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. On the chart below you may find most common orders of growth of algorithms specified in Big O notation.
Source: Big O Cheat Sheet.
Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.
Big O Notation  Type  Computations for 10 elements  Computations for 100 elements  Computations for 1000 elements 

O(1)  Constant  1  1  1 
O(log N)  Logarithmic  3  6  9 
O(N)  Linear  10  100  1000 
O(N log N)  n log(n)  30  600  9000 
O(N^2)  Quadratic  100  10000  1000000 
O(2^N)  Exponential  1024  1.26e+29  1.07e+301 
O(N!)  Factorial  3628800  9.3e+157  4.02e+2567 
Data Structure Operations Complexity
Data Structure  Access  Search  Insertion  Deletion  Comments 

Array  1  n  n  n  
Stack  n  n  1  1  
Queue  n  n  1  1  
Linked List  n  n  1  n  
Hash Table    n  n  n  In case of perfect hash function costs would be O(1) 
Binary Search Tree  n  n  n  n  In case of balanced tree costs would be O(log(n)) 
BTree  log(n)  log(n)  log(n)  log(n)  
RedBlack Tree  log(n)  log(n)  log(n)  log(n)  
AVL Tree  log(n)  log(n)  log(n)  log(n)  
Bloom Filter    1  1    False positives are possible while searching 
Array Sorting Algorithms Complexity
Name  Best  Average  Worst  Memory  Stable  Comments 

Bubble sort  n  n^{2}  n^{2}  1  Yes  
Insertion sort  n  n^{2}  n^{2}  1  Yes  
Selection sort  n^{2}  n^{2}  n^{2}  1  No  
Heap sort  n log(n)  n log(n)  n log(n)  1  No  
Merge sort  n log(n)  n log(n)  n log(n)  n  Yes  
Quick sort  n log(n)  n log(n)  n^{2}  log(n)  No  Quicksort is usually done inplace with O(log(n)) stack space 
Shell sort  n log(n)  depends on gap sequence  n (log(n))^{2}  1  No  
Counting sort  n + r  n + r  n + r  n + r  Yes  r  biggest number in array 
Radix sort  n * k  n * k  n * k  n + k  Yes  k  length of longest key 
Project Backers
You may support this project via â¤ï¸ï¸ GitHub or â¤ï¸ï¸ Patreon.
Folks who are backing this project â = 1
Author
A few more projects and articles about JavaScript and algorithms on trekhleb.dev
Top Related Projects
Algorithms and Data Structures implemented in JavaScript for beginners, following best practices.
💯 Curated coding interview preparation materials for busy software engineers
Learn how to design largescale systems. Prep for the system design interview. Includes Anki flashcards.
Everything you need to know to get the job.
A complete computer science study plan to become a software engineer.
⚡️ Front End interview preparation materials for busy engineers
Convert designs to code with AI
Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.
Try Visual Copilot