Computer Science in JavaScript

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.

Description

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.

Demo

Hosted on GitHub Pages, Demo

Development

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

Tests run by npm test

This project was bootstrapped with Create React App

Author

by Yuliia (Julia) Dizhak

created on 12/21/17

Main Algorithms implementation

• Bitwise

  • 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)

  • Check if number is even or odd

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

• Math (General)

• String manipulation

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

• Array

  • Clone arrays
  • Merge arrays

• 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)

• Search: linear and binary search

  • Linear search
  • Binary search (iterative, recursion)

• 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)	+	+
  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)	-	-

• 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)

• Binary Tree

  • 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(node) recursion	O(logn)	0(n)
  insert(node) Iteratively	O(logn)	0(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)

• Recursion

  • Factorial
  • Fibonacci Number (recursion, iterative)

Leetcode problems solving

• Bitwise operators

  • 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)

  • 231. Power of two (and more approaches)

  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)

  • 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)

• Math / Number

  • 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)

• String manipulation

  • 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)

  • 468. Validate IP address

  Approaches:	Time	Space
  Regex	O(1)	0(1)
  Divide and Conquer	O(n)	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]

  • [771. Jewels and Stones]

  • 438. Find all anagrams

  • [387. First Unique Character in a String]

  • [771. Jewels and Stones]

• Array

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

  • 26. Remove duplicates from sorted array (Two pointers: slow and fast runner)

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

  • 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)

  • 229. Majority element II

  Approaches:	Time	Space
  Hash	O(n)	O(n)
  Voting	O(?)	0(?)

  • 997. Find the Judge in the town

  • 53. Maximum subarray: approach ...

  • 75. Sort colors

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

  • 66 Plus one

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

• Hash

  • 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)

• 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)

• 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)

• 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)

  • 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)

  • 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)

  • 797. All paths from source target

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

• 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)

• DP[dynamic programming]

  • 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

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

  • 70 Climbing stairs

  Approaches:	Time	Space
  Brute force	O(^2n)	0(n)
  	O()	0()

OOP in JS

• Implementation
  • Stop watch

Available Scripts

In the project directory, you can run:

npm start

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.

npm test

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

Folder structure

The most recent packages are found in these directories:

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

TODO:

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