The repo contains JavaScript implementations of different famous computer science algorithms.

As well below you will find solution for leetcode problems divided by dependency of topic relation.

Collection of classic computer science paradigms, algorithms, and approaches written in JavaScript. As well contains description and characteristics: runtime or complexity. Without using in-built methods of JavaScript, for example, sort(), reverse() and etc. Solutions include as well measuring of time complexity.

Hosted on GitHub Pages, Demo

Technology ES6, Yarn, Babel, Jest with a syntax highlighter Highlightjs.

Tests run by npm test

This project was bootstrapped with Create React App

by Yuliia (Julia) Dizhak started on 12/21/17

• Strings manipulation

  • Get all substrings

  Complexity:	Time	Space
  iterative, 2 loops	O(n^2)	0(?)

• Array

  • Array built-in methods

  Complexity:	Time	Space
  push	O(1)	0(1)
  pop	O(1)	0(1)
  shift	O(n)	0(1)
  unshift	O(n)	0(1)
  delete	O(n)	0(1)
  reverse, splice, slice, concat	O(n)	0(1)

• Linked Lists

  • Singly Linked List Implementation

  Complexity:	Time	Space
  get(index)	O(n)	0(1)
  addAtHead(val)	O(1)	0(1)
  addAtTail(val)	O(n)	0(1)
  addAtIndex(index, val)	O(n)	0(1)
  deleteAtIndex(index)	O(n)	0(1)

• Stack implementation

  • Stack via Array

  • Stack via Singly Linked List

  Complexity:	Time	Space
  All operations	O(1)	0(N)?

  • Stack via String

• Queue implementation

  • Queue via Array

  • Queue via Singly Linked List

  Complexity Time:	enqueue	dequeue
  1 Pointer (head)	O(n)	0(1)
  2 Pointers (head and tail)	O(1)	0(1)

• Hash implementation

  • HashSet via object

  Complexity:	time	space
  add	O(1)	0(1)
  remove	O(1)	0(1)
  contains	O(1)	0(1)

• Binary Tree (BT)

  • BT

  Complexity:	Time	Space
  insert iterative + Queue	O(log n)	0(1)
  insert(node) recursion	O(?)	0(?)
  ...

• Binary Tree Traversal

  • Depth-first search: Preorder

  Approaches:	Time	Space
  DFS+ Stack	O(n)	0(h)
  Recursion	O(n)	0(n)

  • BFS: Level order and bottom traversal

  Approaches:	Time	Space
  Iterative + Queue	O(n)	0(n/2 = n)

  • Level order zigzag traversal

  Approaches:	Time	Space
  BFS + Queue	O(n)	0(n)
  Recursion	O(n)	0(n)

• Binary Search Tree (BST) Implementation

  • BST implementation

  Complexity:	Time	Space
  Insert Recursive / iterative	O(log n)	0(n) / O(1)
  ...

• Heap

  • Max Binary Heap

  Complexity:	Time	Space
  insert(val)	O(log n)	0(1)
  deleteMax	O(log n)	O(1)
  max	O(1)	O(1)

• Common bit operations

  • Common bit tasks: getBit(n,i), setBit(n,i), toggleBit(n,i)

  Bit task	Approach	Time/Space
  getBit(num, i)	mask + AND	O(1)
  setBit(num, i)	mask + OR	O(1)
  clearBit(num, i)	~mask + AND	O(1)
  toggleBit(num, i)	XOR	O(1)

• Search: linear and binary

  • Linear search

  • Binary search (iterative, recursion)

  Search name	O	Ω	Space
  Linear Search	O(n)	Ω(1)	O(1)
  Binary Search	O(log n)	Ω(1)	O(1)

• Sorting

  • Bubble sort

  • Selection sort

  • Insertion sort

  • Shell sort

  • Merge sort

  • Quick sort: Hoare and Lomuto partition schema

  • Heapsort

  Sort name	Ω	θ	O	Space	Stable	Adaptive
  Bubble sort	Ω(n)	θ(n^2)	O(n^2)	O(1)	+	+
  Selection sort	Ω(n^2)	θ(n^2)	O(n^2)	O(1)	-	-
  Insertion sort	Ω(n)	θ(n^2)	O(n^2)	O(1)/O(n)	+	+
  Shell sort	Ω(n)	θ(n^2)	O(n^2)	O(1)
  Merge sort	Ω(NlogN)	θ(NlogN)	O(NlogN)	O(N)	+	-
  Quick sort	Ω(NlogN)	θ(NlogN)	O(n^2)	O(NlogN)	-	-
  Heapsort	Ω(NlogN)	θ(NlogN)	O(NlogN)	O(1)	-	-

• Bitwise operators

  • Check if number is even or odd

  Approaches:	Time	Space
  AND	O(1)	O(1)
  XOR	O(1)	O(1)

  • 476. Number complement / 1009. Complement of Base 10 Integer

  Approaches:	Time	Space
  Bit Shift + xor (2)	O(1)	0(1)
  toString and parseInt	O(1)	0(1)
  decimal to Binary + Stack	O(log n)	0(log n)
  N + complement = 1	O(log n)	0(1)

  • 231. Power of two

  Approaches:	Time	Space
  Iterative: keep divide by 2	O(log n)	0(1)
  Math + toString	O(n)	O(1)
  Bit Manipulation Trick	O(1)	O(1)

  • 326. Power of three

  Approaches:	Time	Space
  Iterative: keep divide by 3	O(log_3n)	0(1)
  Integer limitations	O(1)	0(1)

  • 342. Power of four

  Approaches:	Time	Space
  Iterative: keep divide by 4	O(log_4n)	0(1)
  Bit Manipulation Trick	O(1)	O(1)
  Divisible by 3	O(1)	O(1)
  Ends with 4 or 6	O(1)	O(1)

  • 693. Binary Number of Alternating Bits

  Approaches:	Time	Space
  Convert to Sting	O(1)	0(1)
  Prev + XOR	O(1)	O(1)
  XOR	O(1)	O(1)

  • 136. Single Number

  Approaches:	Time	Space
  Bitwise XOR	O(n)	0(1)
  Hash	O(n)	O(n)
  Brute force	O(n^2)	O(1)

  • 260. Single Number III

  Approaches:	Time	Space
  Bitwise XOR	O(n)	0(1)

  • 191. Number of bits

  Approaches:	Time	Space
  Loop + Flip	O(1)	0(1)
  Bit trick manipulation	O(1)	O(1)

  • 461. Hamming distance

  Approaches:	Time	Space
  Bit trick manipulation	O(1)	O(1)
  XOR + toString	O(n)	O(1)

  • 190. Reverse bits

  Approaches:	Time	Space
  Bit by bit	O(1)	O(1)
  Memoization	O(1)	O(1)
  Mask and shift	O(1)	O(1)

• Number (Math)

  • 171. Excel sheet column number

  Approaches:	Time	Space
  Math + loop	O(n)	0(1)
  Recursion	O(n)	0(n)

  • 1103. Distribute candies to people

  Approaches:	Time	Space
  Iterative	O(n)	0(num_people)
  Loop + min	O(sqrt n)	0(num_people)
  Math (Gauss)	O(sqrt n)	0(num_people)

  • 263. Ugly number

  Approaches:	Time	Space
  Recursion	O(log N)	0(log N)?
  Greatest divide by [2,3,4]	O(log N)	0(1)

  • 264. Ugly number II

  Approaches:	Time	Space
  Brute force	O(n)	0(1)
  Generate all ugly numbers	O(n log n)	0(n)
  DP	O(n)	0(n)

  • 1344. Angle between hands of clock

  Approach:	Time	Space
  Math	O(1)	0(1)

  • 258. Add digits

  Approach:	Time	Space
  Recursion	O(n)	0(n)
  Iteration	O(n)	0(1)
  Math	O(1)	0(1)

  • 1041. Robot bounded in circle

  Approach:	Time	Space
  Math + rotation	O(n)	0(1)
  Math	O(n)	0(1)

  • 174. Largest Number

  Approach:	Time	Space
  Sort	O(nlogn)	0(n) / O(1)

• String manipulation

  • Reverse a string (swap, recursion, 2 pointers)

  • 541. Reverse a string II (2 pointers depends on k)

  • 392. Is subsequence

  Approaches:	Time	Space
  Two pointers	O(n)	0(1)
  Recursion	O(n)	0(n)

  • 520. Detect capital

  Approaches:	Time	Space
  Use substr	O(n)	0(1)
  Character by character	O(n)	0(1)
  Regex	O(n) / O(2^n)	0(1)

  • 125. Valid palindrome

  Approaches:	Time	Space
  2 pointers	O(n)	0(1)
  Use reverse	O(n)	0(1)

  • 406. Longest palindrome

  Approaches:	Time	Space
  Hash	O(n)	0(n) / O(1)
  Greedy	O(n)	0(n) / O(1)

  • 459. Repeated substr pattern

  Approaches:	Time	Space
  Loop	O(n)	O(1)

  • 796. Rotate string

  Approaches:	Time	Space
  Brute force	O(n^2)	O(n)
  Hash	?	?
  Simple check	O(n)	O(n)

  • 486. Validate IP address

  Approaches:	Time	Space
  Regex	O(1)	0(1)
  Divide and Conquer	O(n)	0(1)

  • 58. Length of last word

  Approaches:	Time	Space
  Loop backward + tail	O(n)	0(1)
  Regex	O(1)	0(1)

  • 3. Longest substring without repeating characters

  Approaches:	Time	Space
  Brute force	O(n^3)	O(min(n,m))
  Sliding window + Hash	O(2n)=O(n)	O(min(n,m))

  • 151. Reverse words in string

  Approaches:	Time	Space
  Two pointers (in-place)	O(n)	O(1)
  Two pointers + trim	O(n)	O(n))
  reverse, split, trim	O(n)	O(n))

  • [383. Ransom Note]

  • 387. First Unique Character in a String

  Approaches:	Time	Space
  Hash / Map	O(n)	O(n) / O(1)
  Brute-force (indexOf, lastIndexOf)	O(n^2)	O(1)
  Use Array	O(n)	O(n) / O(1)

  • Is string unique

  Approaches:	Time	Space
  Brute-force (lastIndexOf)	O(n^2)	O(1)
  Hash	O(n)	O(n)/ O(1)
  Sort	O(n log n)	O(n)
  Set	O(n)	O(n)

  • 1446. Consecutive Characters

  Approaches:	Time	Space
  1 pass	O(n)	O(1)
  Use Array	O(n)	O(n)

  • [771. Jewels and Stones]

  • 438. Find all anagrams

  • [387. First Unique Character in a String]

  • [771. Jewels and Stones]

  • 389. Find difference

  Approaches:	Time	Space
  Hash	O(n)	0(n)
  Iterative	O(n)	0(1)
  XOR	O(n)	0(1)

• Array

  • Clone arrays

  • Merge arrays

  Approaches:	Time	Space
  Spread operator	O(n log n)	0(1)
  Iterative + create a new arr	O(n+m)	0(1)

  • Find Two Numbers that Add up to value

  Approaches:	Time	Space
  Brute force	O(n^2)	0(1)
  Sort + binary search	O(n log n)	0(1)
  Sort + 2 pointers	O(n log n)	0(1)

  • 268. Missing number (approach: Gauss, sorting, hash)

  • 26. Remove duplicates from sorted array

  Approaches:	Time	Space
  Hash and Array	O(n)	0(2n) = O(n)
  2 pointers: slow and fast	O(n)	0(1)
  Set	O(n)	0(n)
  Array.splice	O(n) ?	0(1)

  • 540. Single element in sorted array (approach: Brute force, binary search, BS only on even indexes)

  • 643. Max average subarray I

  Approaches:	Time	Space
  Brute force	O(n^2)	0(1)
  Sliding window	O(n)	O(1)
  Cumulative Sum	O(n)	O(1)

  • 209. Minimum Size Subarray Sum

  Approaches:	Time	Space
  Brute force	O(n^2)	0(1)
  Shrink Sliding window	O(n)	O(1)
  Sort	O(?)	O(?)

  • 169. Majority element

  Approaches:	Time	Space
  Brute force	O(n^2)	0(1)
  Hash	O(n)	O(n)
  Sorting	O(nlogn)	O(1) / O(n)
  Voting	O(n)	O(1)
  Randomization index	O(infinite)/O(n)	O(1)
  Divide and Conquer	O(log n)	O(log n)

  • 229. Majority element II

  Approaches:	Time	Space
  Hash	O(n)	O(n)
  Boyer-Moore Voting	O(n)	0(1)

  • 118. Pascals triangle

  Approaches:	Time	Space
  Array (loop)	O(numsRows^2)	O(numsRows^2)

  • 119. Pascals triangle II

  Approaches:	Time	Space
  DP	O(rowIndex^2)	O(k)
  Recursion	O(2^rowIndex)	O(k)

  • 1638. Sort Array by Increasing Frequency

  Approaches:	Time	Space
  Hash + sort	O(n log n)	O(n)
  Map + sort	O(n log n)	O(n)

  • 997. Find the Judge in the town

  • 66. Plus one

  Approach:	Time	Space
  Loop	O(n)	O(n)
  Math.pow	O(n)	O(n)

  • 422. Find all duplicates in Array

  Approach:	Time	Space
  Hash	O(n)	O(n)
  Sort + 2 pointers	O(n log n)	O(1)
  Use Array	O(n)	O(n)
  Mutate Array (negative indexes)	O(n)	O(1)

  • 41. First missing positive

  Approach:	Time	Space
  Hash	O(n)	O(n)
  Use Array	O(n)	O(n)

  • 849. Maximize Distance to Closest Person

  Approach:	Time	Space
  Next Array	O(n)	O(n)

• Array Sorting

  • 75. Sort colors

  Approach:	Time	Space
  2 pointers	O(n)	O(1)

  • 969. Pancake sorting

  Approach:	Time	Space
  Find max + 2 flips	O(n^2)	O(n)
  Like a bubble sort	O(n^2)	O(n)

• Intervals (Array, sort)

  • 1288. Remove Covered Intervals

  Approach:	Time	Space
  Sort left by asc, right by desc	O(nlogn)	O(1)
  Sort	O(nlogn)	O(1)

  • 57. Insert interval

  Approach:	Time	Space
  Iterative	O(n)	O(1)

  • Car pooling

  Approach:	Time	Space
  Bucket sort	O(n)	O(m = 1001)
  Same timestamp as Hash	O(n)	O(n)

• Singly Linked List

  • 237. Delete node in Linked List

  Approach	Time	Space
  Swap with next node	O(1)	O(1)
  Usual way: find prev	O(n)	O(1)

  • 1290. Convert Binary Number in a Linked List to Integer

  Approach	Time	Space
  Binary representation	O(n)	O(1)
  Bit manipulation	O(n)	O(1)

  • 147. Insertion sort list

  Approach	Time	Space
  Insertion sort	O(n^2)	O(1)

  • 206. Reverse Linked List

  Approach	Time	Space
  Iterative	O(n)	O(1)

  • 143. Reorder Linked List

  Approach	Time	Space
  Brute force	O(n^2)	O(1)

• Doubly Linked List

  • 430. Flatten a multilevel Doubly Linked List

  Approach	Time	Space
  Iterative	O(n)?	O(1)
  Use stack	O(?)	O(?)

• Stack

  • 155. Min Stack

  Approaches:	Time	Space
  2 Stacks	O(1)	0(n)
  1 Stack + min pairs	O(1)	O(n)
  Improved 2 Stacks	O(1)	O(n)

  • 716. Max Stack

  Approach: 2 Stacks	Time	Space
  popMax()	O(n)	0(n)
  other operations	O(1)	O(n)

• Queue

  • 232. Queue use 2 stacks

  Complexity:	Time	Space
  enqueue	O(1)	0(1)
  dequeue	O(n)	0(1)

• Hash

  • 1. Two sum

  Approaches:	Time	Space
  Brute force	O(n^2)	O(1)
  2-pass Hash table	O(n)	O(n)
  1-pass Hash table	O(n)	O(n)

  • 380. Insert Delete GetRandom O(1)

  Approach	Time	Space
  Array + Map: init		O(m+n)
  insert	O(1)	O(1)
  remove	O(1)	O(1)
  getRandom	O(1)	O(1)

  • 957. Prison Cells After N Days

  Approach	Time	Space
  Hash + catch cycle	O(1)	O(1)

• Tree, Binary Tree

  • 226. Invert a Binary Tree (recursive)

  Approaches:	Time	Space
  Recursion	O(n)	0(n)

  • 104. Maximum depth of binary tree

  Approaches:	Time	Space
  Recursion	O(n)	0(n)

  • 111. Minimum depth of binary tree

  Approaches:	Time	Space
  Recursion	O(n)	0(n) / O(logn)

  • 100. Same Tree

  Approaches:	Time	Space
  Recursion	O(n)	0(logn)/O(n)
  Iterative DFS	O(n)	0(logn)/O(n)

  • 106. Construct BT from inorder, preorder

  Approaches:	Time	Space
  Recursion	O(n^2)	0(n^2)
  Hash indexes from inorder	O(n)	O(n)
  Map indexes from inorder without pop	O(n)	O(n)

  • 222. Count complete tree nodes

  Approaches:	Time	Space
  Recursion	O(log(n)^2)	0(n)

• BST (Binary Search Tree)

  • 701. Insert into a BST

  Approaches:	Time	Space
  Recursion	O(log n) / O(h)	0(h)
  Iterative	O(log n) / O(h)	0(1)

  • 700. Search in BST

  Approaches:	Time	Space
  Recursion	O(logn) / O(n)	0(h)
  Iterative	O(logn) / O(n)	0(1)

• Graph

  • 733. Flood Fill

  Approaches:	Time	Space
  DFS (recursion + visited flag)	O(N)	0(N)
  BFS (queue + visited flag)	O(N)	0(N)

  • 967. Numbers With Same Consecutive Differences

  Approaches:	Time	Space
  DFS (+last digit)	O(N * 2^N)	O(2^N)

  • 994. Rotting oranges

  Approaches:	Time	Space
  BFS + Hashes	O(n*m)	O(n)
  BFS (Queue)	O(n*m)	O(n)

  • 797. All paths from source target

  Approaches:	Time	Space
  BFS+Queue	O(n^2 * 2^n)	O(2^n)

• Recursion

  • Factorial

  • Fibonacci Number (recursion, iterative)

  Approaches:	O	T	Space
  Recursion	O(2^n)	0(?)	0(n)
  Iterative	O(n)	0(?)	0(1)
  Iterative Top-Down	O(n)	0(?)	0(1)

• Divide & Conquer

  • 215. Find the kth largest element

  Approaches:	O	T	Space
  Sort	O(log n)	0(log n)	0(1)
  Quick-select	O(n^2)	0(n)	0(1)

• Binary Search

  • 278. First Bad version

  • 35. Search insert position

  Approaches:	Time	Space
  Binary search	O(log n)	0(1)
  Linear Search	O(n)	O(1)

  • 441. Search insert position

  Approaches:	Time	Space
  Binary search	O(log n)	0(1)
  Math	O(1)	O(1)

  • 153 Find minimum in rotated sorted array

  Approaches:	Time	Space
  Brute force	O(n)	O(1)
  Binary search	O(log n)	0(1)

  • 154. Find minimum in rotated sorted array

  Approaches:	Time	Space
  Brute force	O(n)	0(1)
  Binary search	O(log n)	0(1)

  • 528. Random pick with weight (accumulation sum + binary search)

• Greedy

  • 1029. Two city Scheduling

  Approaches:	Time	Space
  Greedy	O(nlogn)	0(1)

  • 621. Task scheduler

  Approaches:	Time	Space
  Greedy + map	O(n)	0(1)
  Greedy + hash	O(n)	0(n)

  • 134. Gas station

  Approaches:	Time	Space
  Iterative 1 pass	O(n)	0(1)
  Iterative 2 passes	O(n)	0(1)
  Brute force	O(n^2)	0(1)

• DP [dynamic programming]

  • 53. Maximum subarray

  Approaches:	Time	Space
  Brute force + sliding window	O(n^3)	O(1)

  • 152. Max product subarray

  Approaches:	Time	Space
  Brute force + sliding window	O(n^3)	O(1)
  Store prev max and min	O(n)	O(1)
  DP	O(n)	O(1)

  • 518. Coin change 2

  • 96. Unique binary search trees

  Approaches:	Time	Space
  DP	O(n^2)	0(n)

  • 121. Best time to buy and sell stock 1

  Approaches:	Time	Space
  Brute force	O(n^2)	0(1)
  One pass	O(n)	0(1)
  Find min price so far	O(n)	0(1)
  DP	O(n)	0(n)

  • 122. Best time to buy and sell stock II

  Approaches:	Time	Space
  Greedy	O(n)	0(1)

  • 70 Climbing stairs

  Approaches:	Time	Space
  Brute force	O(^2n)	0(n)
  DP: bottom-up	O(n)	0(n)

• Backtracking

  • 46. Print all permutations

  Approaches:	Time	Space
  Backtracking	O(n!)	0(?)

  • 216. Combination sum III

  Approaches:	Time	Space
  Backtracking	O(9!* K / (9-K)!)	0(k)

• Implementation
  • Stop watch

In the project directory, you can run:

Runs the app in the development mode.
Open http://localhost:3000 to view it in the browser.

The page will reload if you make edits.
You will also see any lint errors in the console.

Launches the test runner in the interactive watch mode.
See the section about running tests for more information.

The most recent packages are found in these directories:

• src/ds - the implementation source code
• src/ds/***.spec.js - tests for the implementation source code

• scrollTo works with bug
• details toggle works with bug (sometimes)
• display level: beginner, medium, ... (like corners)
• generate test coverage
• performance test
• seo