Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
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 started on 12/21/17
Complexity terms
| Symbol | Name | Performance |
|---|---|---|
| Ω | big-omega | best-case performance |
| θ | big-theta | average |
| O | big-oh | worst |
Main Data Structures implementations by Javascript
-
Strings manipulation
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
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
Complexity: Time Space All operations O(1) 0(N)? -
Queue implementation
Complexity Time: enqueue dequeue 1 Pointer (head) O(n) 0(1) 2 Pointers (head and tail) O(1) 0(1) -
Hash implementation
Complexity: time space add O(1) 0(1) remove O(1) 0(1) contains 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
Approaches: Time Space DFS+ Stack O(n) 0(h) Recursion O(n) 0(n) Approaches: Time Space Iterative + Queue O(n) 0(n/2 = n) Approaches: Time Space BFS + Queue O(n) 0(n) Recursion O(n) 0(n) -
Binary Search Tree (BST) Implementation
Complexity: Time Space Insert Recursive / iterative O(log n) 0(n) / O(1) ... -
Heap
Complexity: Time Space insert(val) O(log n) 0(1) deleteMax O(log n) O(1) max O(1) O(1)
Bitwise operator in JS
-
Common bit operations
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)
Searching and Sorting
-
Search: linear and binary
Search name O Ω Space Linear Search O(n) Ω(1) O(1) Binary Search O(log n) Ω(1) O(1) -
Sorting
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) - -
Problem solving on leetcode
-
Bitwise operators
Approaches: Time Space AND O(1) O(1) XOR O(1) O(1) 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) 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) Approaches: Time Space Iterative: keep divide by 3 O(log_3n) 0(1) Integer limitations O(1) 0(1) 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) Approaches: Time Space Convert to Sting O(1) 0(1) Prev + XOR O(1) O(1) XOR O(1) O(1) Approaches: Time Space Bitwise XOR O(n) 0(1) Hash O(n) O(n) Brute force O(n^2) O(1) Approaches: Time Space Bitwise XOR O(n) 0(1) Approaches: Time Space Loop + Flip O(1) 0(1) Bit trick manipulation O(1) O(1) Approaches: Time Space Bit trick manipulation O(1) O(1) XOR + toString O(n) O(1) Approaches: Time Space Bit by bit O(1) O(1) Memoization O(1) O(1) Mask and shift O(1) O(1) -
Number (Math)
Approaches: Time Space Math + loop O(n) 0(1) Recursion O(n) 0(n) 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) Approaches: Time Space Recursion O(log N) 0(log N)? Greatest divide by [2,3,4] O(log N) 0(1) Approaches: Time Space Brute force O(n) 0(1) Generate all ugly numbers O(n log n) 0(n) DP O(n) 0(n) Approach: Time Space Math O(1) 0(1) Approach: Time Space Recursion O(n) 0(n) Iteration O(n) 0(1) Math O(1) 0(1) Approach: Time Space Math + rotation O(n) 0(1) Math O(n) 0(1) Approach: Time Space Sort O(nlogn) 0(n) / O(1) -
String manipulation
Approaches: Time Space Two pointers O(n) 0(1) Recursion O(n) 0(n) Approaches: Time Space Use substr O(n) 0(1) Character by character O(n) 0(1) Regex O(n) / O(2^n) 0(1) Approaches: Time Space 2 pointers O(n) 0(1) Use reverse O(n) 0(1) Approaches: Time Space Hash O(n) 0(n) / O(1) Greedy O(n) 0(n) / O(1) Approaches: Time Space Loop O(n) O(1) Approaches: Time Space Brute force O(n^2) O(n) Hash ? ? Simple check O(n) O(n) Approaches: Time Space Regex O(1) 0(1) Divide and Conquer O(n) 0(1) Approaches: Time Space Loop backward + tail O(n) 0(1) Regex O(1) 0(1) Approaches: Time Space Brute force O(n^3) O(min(n,m)) Sliding window + Hash O(2n)=O(n) O(min(n,m)) 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]
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) 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) Approaches: Time Space 1 pass O(n) O(1) Use Array O(n) O(n) -
[771. Jewels and Stones]
-
[387. First Unique Character in a String]
-
[771. Jewels and Stones]
Approaches: Time Space Hash O(n) 0(n) Iterative O(n) 0(1) XOR O(n) 0(1) -
Array
Approaches: Time Space Spread operator O(n log n) 0(1) Iterative + create a new arr O(n+m) 0(1) 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) 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) Approaches: Time Space Brute force O(n^2) 0(1) Sliding window O(n) O(1) Cumulative Sum O(n) O(1) Approaches: Time Space Brute force O(n^2) 0(1) Shrink Sliding window O(n) O(1) Sort O(?) O(?) 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) Approaches: Time Space Hash O(n) O(n) Boyer-Moore Voting O(n) 0(1) Approaches: Time Space Array (loop) O(numsRows^2) O(numsRows^2) Approaches: Time Space DP O(rowIndex^2) O(k) Recursion O(2^rowIndex) O(k) Approaches: Time Space Hash + sort O(n log n) O(n) Map + sort O(n log n) O(n) Approach: Time Space Loop O(n) O(n) Math.pow O(n) O(n) 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) Approach: Time Space Hash O(n) O(n) Use Array O(n) O(n) Approach: Time Space Next Array O(n) O(n) -
Array Sorting
Approach: Time Space 2 pointers O(n) O(1) Approach: Time Space Find max + 2 flips O(n^2) O(n) Like a bubble sort O(n^2) O(n) -
Intervals (Array, sort)
Approach: Time Space Sort left by asc, right by desc O(nlogn) O(1) Sort O(nlogn) O(1) Approach: Time Space Iterative O(n) O(1) Approach: Time Space Bucket sort O(n) O(m = 1001) Same timestamp as Hash O(n) O(n) -
Singly Linked List
Approach Time Space Swap with next node O(1) O(1) Usual way: find prev O(n) O(1) Approach Time Space Binary representation O(n) O(1) Bit manipulation O(n) O(1) Approach Time Space Insertion sort O(n^2) O(1) Approach Time Space Iterative O(n) O(1) Approach Time Space Brute force O(n^2) O(1) -
Doubly Linked List
Approach Time Space Iterative O(n)? O(1) Use stack O(?) O(?) -
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) Approach: 2 Stacks Time Space popMax() O(n) 0(n) other operations O(1) O(n) -
Queue
Complexity: Time Space enqueue O(1) 0(1) dequeue O(n) 0(1) -
Hash
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) Approach Time Space Array + Map: init O(m+n) insert O(1) O(1) remove O(1) O(1) getRandom O(1) O(1) Approach Time Space Hash + catch cycle O(1) O(1) -
Tree, Binary Tree
Approaches: Time Space Recursion O(n) 0(n) Approaches: Time Space Recursion O(n) 0(n) Approaches: Time Space Recursion O(n) 0(n) / O(logn) Approaches: Time Space Recursion O(n) 0(logn)/O(n) Iterative DFS O(n) 0(logn)/O(n) 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) Approaches: Time Space Recursion O(log(n)^2) 0(n) -
BST (Binary Search Tree)
Approaches: Time Space Recursion O(log n) / O(h) 0(h) Iterative O(log n) / O(h) 0(1) Approaches: Time Space Recursion O(logn) / O(n) 0(h) Iterative O(logn) / O(n) 0(1) -
Graph
Approaches: Time Space DFS (recursion + visited flag) O(N) 0(N) BFS (queue + visited flag) O(N) 0(N) Approaches: Time Space DFS (+last digit) O(N * 2^N) O(2^N) Approaches: Time Space BFS + Hashes O(n*m) O(n) BFS (Queue) O(n*m) O(n) Approaches: Time Space BFS+Queue O(n^2 * 2^n) O(2^n)
Programming methods/paradigms
-
Recursion
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
Approaches: O T Space Sort O(log n) 0(log n) 0(1) Quick-select O(n^2) 0(n) 0(1) -
Binary Search
Approaches: Time Space Binary search O(log n) 0(1) Linear Search O(n) O(1) Approaches: Time Space Binary search O(log n) 0(1) Math O(1) O(1) Approaches: Time Space Brute force O(n) O(1) Binary search O(log n) 0(1) Approaches: Time Space Brute force O(n) 0(1) Binary search O(log n) 0(1) -
Greedy
Approaches: Time Space Greedy O(nlogn) 0(1) Approaches: Time Space Greedy + map O(n) 0(1) Greedy + hash O(n) 0(n) 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]
Approaches: Time Space Brute force + sliding window O(n^3) O(1) 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) Approaches: Time Space DP O(n^2) 0(n) 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) Approaches: Time Space Greedy O(n) 0(1) Approaches: Time Space Brute force O(^2n) 0(n) DP: bottom-up O(n) 0(n) -
Backtracking
Approaches: Time Space Backtracking O(n!) 0(?) Approaches: Time Space Backtracking O(9!* K / (9-K)!) 0(k)
OOP in JS
- Implementation
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/ds- the implementation source codesrc/ds/***.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