algm

A fast algorithm library for JavaScript/TypeScript.

Problem

When you participate in an algorithm competition or code algorithm problems online such as leetcode, you may choose c++,java,python. Because they have the built-in library like STL that contains priority queue,order set etc.

Installation

npm install algm

Documentation

You can find the algm documentation on the website.

Why algm?

Safe

importafrom'algm';constarr=Array(125625).fill(0);//Maximum call stack size exceeded in nodejsMath.max(...arr);//safea.max(arr);// the recursive version postorder traversal may result in maximum call stack error// a.postorder internal use iterationa.postorder(root,(node,fatherNode)=>{console.log(node);});

Contains many frequently used functions

importafrom'algm';// init an array with an initial value of 0a.initArray(4);// => [0,0,0,0]// init a two-dimensional array with an initial value of 0a.init2Array(3,4);// => [[0,0,0,0],[0,0,0,0],[0,0,0,0]]// get the max valuea.max(1,3,2);// => 3a.max([1,3,2]);// => 3// get the min valuea.min(1,3,2);// => 1a.min([1,3,2]);// => 1// compute the sum of an arraya.sum([1,2,3]);// => 6// get the last element of an arraya.last([3,2,1]);// => 1// return a new arr that does not contains duplicate elements.a.unique([1,1,2,2,2,6,1]);//=> [1,2,6]// sort the array in ascending ordera.sortA([3,1,2]);// => [1, 2, 3]a.sortA([{height: 3},{height: 2},{height: 1}],x=>x.height);// => [{ height: 1 }, { height: 2 }, { height: 3 }]a.sortD([3,1,2]);// => [3, 2, 1]a.sortD([{height: 3},{height: 2},{height: 1}],x=>x.height);// => [{ height: 3 }, { height: 2 }, { height: 1 }]// compute the greatest common divisor of a and ba.gcd(4,2);// => 2a.gcd(9,6);// => 3// Randomly returns integers in [min, max)a.random(2,8);// => 4// Compute the number of permutations c(n,m)=n*(n-1)*...(n-m+1)/(m!)// the result is biginta.c(5,2);// => 10na.c(5,0);// => 1n// Compute the number of permutations,// then take the remainder of modulo 10 * * 9 + 7a.cm(5,2);// => 10a.cm(5,0);// => 1// Compute the remainder of m mod n// The main difference with m%n is that a.mod always return nonnegative number.a.mod(2,3);// => 2a.mod(-2,3);// => 1-2%3;// => -2a.mod(-2,2);// => 0

data structure

• priority queue

  max priority queue

  constinput=[4,3,1];constmaxP=newMaxPQ(input);maxP.max();//=> 4maxP.insert(5);maxP.max();//=> 5maxP.insert(8);maxP.max();//=> 8maxP.delMax();maxP.max();//=> 5

  Provide the specified key

  constinput=[{name: 'xiao',age: 21},{name: 'wang',age: 22},{name: 'li',age: 25},];constmaxP=newMaxPQ(input,v=>v.age);constm=maxP.max();//=> { name: 'li', age: 25 }

• SkipList

  a probabilistic data structure

  search, insert, remove achieve O(Logn) expected performance. max,min cost O(1) time complexity

  constsl=newSkipList();sl.insert(3);sl.insert(1);sl.insert(5);sl.search(1);// => 1sl.remove(1);sl.search(1);// => null

• randomized binary search tree

  search, insert, remove, find the k-th max value achieve O(Logn) expected performance.

  constrbst=newRBST();constarr=[1,7,3];arr.forEach(v=>{rbst.insert(v);});rbst.search(3);// => 3rbst.findKMax(1);// => 7rbst.remove(3);rbst.search(3);// => nullrbst.findKMax(2);// => 1

• Segment tree

  Max segment tree

  Query the maximum value of given range and update the value in O(Logn) time.

  import{MaxArr}from'algm';constmaxArr=newMaxArr([2,3,1,7,9]);const[l,r]=[0,2];// find the maximum value from [l,r]maxArr.query(l,r);//=> 3maxArr.query(0,3);//=> 7maxArr.update(1,9);// arr=[2, 9, 1, 7, 9]maxArr.query(0,3);//=> 9

  Provide the specified key

  import{MaxArr}from'algm';constmaxArr=newMaxArr([{name: 'li',age: 21},{name: 'wang',age: 24},{name: 'xx',age: 23},],node=>node.age);maxArr.query(0,2);//=> { name: 'wang', age: 24 }maxArr.update(0,{name: 'xiao',age: 25});maxArr.query(0,2);//=> { name: 'xiao', age: 25 }

  sum segment tree

  Query the sum of given range and update the value in O(Logn) time.

  import{SumArr}from'algm';constsumArr=newSumArr([2,3,1,7,9]);sumArr.query(0,2);//=> 6sumArr.update(2,4);sumArr.query(0,2);//=> 9

  value segment tree

  Given an array contains all the values,insert the value one by one,and query the number of value in [lower,upper].

  import{ValueArr}from'algm';constarr=[1,2,3,5,7];constvArr=newValueArr(arr);vArr.insert(1);vArr.insert(3);vArr.insert(5);assert.strictEqual(vArr.query(1,5),3);vArr.insert(1);assert.strictEqual(vArr.query(1,5),4);

• union–find

  A data structure that stores a collection of disjoint (non-overlapping) sets. It provides operations for merging sets (union), and finding a representative member(find) of a set.

  import{UnionFind}from'algm';constn=4;constuf=newUnionFind(n);uf.union(0,1);uf.union(1,2);uf.isSameSet(0,2);//=> trueuf.isSameSet(0,3);//=> false

algorithm

• topsort

  topsort({n: 5,edges: [[1,0],[1,3],[3,2],[3,4],],});// => [1,3,4,2,0]

• Hopcroft–Karp algorithm

  a fast bipartite matching algorithms

  hopcroftKarp(5,[[5,6],[5,9],[7,8],[5,9],[6,8],]);// => Map(10){ 0=>6,1=>9,2=>7,3=>5,4=>8,6=>0,7=>2,8=>4,9=>1 }

• manacher a linear time algorithm to find all the palindromic substring

import{getPalindromeArr}from'algm';constpalindromeLengthArr=getPalindromeArr('aba')// The length of the palindrome centered on each vertex// => [1,3,1]