Algorithm Implementation.
Bisect
//////////////////////////////////////////////Template/////////////////////////////////////////////////////////////functionBisect(){return{ insort_right, insort_left, bisect_left, bisect_right }functioninsort_right(a,x,lo=0,hi=null){lo=bisect_right(a,x,lo,hi)a.splice(lo,0,x)}functionbisect_right(a,x,lo=0,hi=null){// > upper_boundif(lo<0)thrownewError('lo must be non-negative')if(hi==null)hi=a.lengthwhile(lo<hi){letmid=parseInt((lo+hi)/2)x<a[mid] ? (hi=mid) : (lo=mid+1)}returnlo}functioninsort_left(a,x,lo=0,hi=null){lo=bisect_left(a,x,lo,hi)a.splice(lo,0,x)}functionbisect_left(a,x,lo=0,hi=null){// >= lower_boundif(lo<0)thrownewError('lo must be non-negative')if(hi==null)hi=a.lengthwhile(lo<hi){letmid=parseInt((lo+hi)/2)a[mid]<x ? (lo=mid+1) : (hi=mid)}returnlo}}LIS(Longest Increasing Subsequence) implementation
constLIS=arr=>{constn=arr.length// memo[j]: 长度为j的最长自增子序列最后一位的index（同长度最后一位最小）. // stores the index k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i// pre[k]: 以arr[k]结尾的LIS，arr[k]之前一个元素的index. // stores the index of the predecessor of X[k] in the longest increasing subsequence ending at X[k] constpre=Array(n),memo=Array(n+1)letlen=0// lengthfor(leti=0;i<n;i++){letlo=1,hi=lenwhile(lo<=hi){letmid=Math.ceil((lo+hi)/2)if(arr[memo[mid]]<arr[i])lo=mid+1elsehi=mid-1}constnewL=lopre[i]=memo[newL-1]memo[newL]=iif(newL>len)len=newL}constres=Array(len)letk=memo[len]for(leti=len-1;i>=0;i--){res[i]=arr[k]k=pre[k]}returnres}// construct. LISconstLIS=X=>{constn=X.lengthconstP=Array(n),M=Array(n+1)letL=0for(leti=0;i<n;i++){letlo=1,hi=Lwhile(lo<=hi){letmid=Math.ceil((lo+hi)/2)if(X[M[mid]]<X[i])lo=mid+1elsehi=mid-1}letnewL=loP[i]=M[newL-1]M[newL]=iif(newL>L)L=newL}letS=Array(L)letk=M[L]for(leti=L-1;i>=0;i--){S[i]=X[k]k=P[k]}returnS}functionconstructLIS(arr){constn=arr.length;constL=Array(n);for(leti=0;i<L.length;i++)L[i]=[];L[0].push(arr[0]);for(leti=1;i<n;i++){for(letj=0;j<i;j++){if(arr[i]>arr[j]&&L[i].length<L[j].length+1){L[i]=L[j].slice();}}L[i].push(arr[i]);}letmax=L[0];for(letxofL){if(x.length>max.length)max=x;}returnmax;}/** * @param {number[]} nums * @return {number} */constlengthOfLIS=function(nums){conststack=[]for(leteofnums){if(stack.length===0||e>stack[stack.length-1]){stack.push(e)continue}letl=0,r=stack.length-1,midwhile(l<r){constmid=l+((r-l)>>1)if(e>stack[mid])l=mid+1elser=mid}stack[l]=e}returnstack.length};Convert base implementation
functionconvertFromBaseToBase(str,fromBase,toBase){constnum=parseInt(str,fromBase);returnnum.toString(toBase);}floorIndex, ceilIndex implementation
functionceilIndex(t,l,r,key){while(r-l>1){letm=(l+(r-l)/2)>>0if(t[m]>=key){r=m}else{l=m}}returnr}functionfloorIndex(t,l,r,key){while(r-l>1){letm=(l+(r-l)/2)>>0if(t[m]<=key){l=m}else{r=m}}returnl}lower_bound implementation
// the first element in the range [first, last) which has a value not less than val.// This means that the function returns the index of the next smallest number just// greater than or equal to that number. If there are multiple values that are equal to val,// lower_bound() returns the index of the first such value.// Like C++'s std::lower_bound. Returns the first index at which// `value` could be inserted without changing the ordering. Assumes// the array is sorted.//// `first` and `last` are indices and `less` is an optionally-specified// function that returns true if// array[i] < value// for some i and false otherwise.//// Usage: lower_bound(array, value, [less])// lower_bound(array, first, last, value, [less])functionlower_bound(array,arg1,arg2,arg3,arg4){letfirst;letlast;letvalue;letless;if(arg3===undefined){first=0;last=array.length;value=arg1;less=arg2;}else{first=arg1;last=arg2;value=arg3;less=arg4;}if(less===undefined){less=function(a,b){returna<b;};}letlen=last-first;letmiddle;letstep;while(len>0){step=Math.floor(len/2);middle=first+step;if(less(array[middle],value,middle)){first=middle;first+=1;len=len-step-1;}else{len=step;}}returnfirst;};upper_bound implementation
/**It returns the first element in the range [first, last) thatis greater than value, or last if no such element is found.*/functionupperBound(array,func){letdiff,len,i,current;len=array.length;i=0;while(len){diff=len>>>1;current=i+diff;if(func(array[current])){len=diff;}else{i=current+1;len-=diff+1;}}returni;}Binary insert implementation
/** * Takes in a __SORTED__ array and inserts the provided value into * the correct, sorted, position. * @param array the sorted array where the provided value needs to be inserted (in order) * @param insertValue value to be added to the array * @param comparator function that helps determine where to insert the value ( */functionbinaryInsert(array,insertValue,comparator=(a,b)=>a-b){/* * These two conditional statements are not required, but will avoid the * while loop below, potentially speeding up the insert by a decent amount. * */if(array.length===0||comparator(array[0],insertValue)>=0){array.splice(0,0,insertValue)returnarray;}elseif(array.length>0&&comparator(array[array.length-1],insertValue)<=0){array.splice(array.length,0,insertValue);returnarray;}letleft=0,right=array.length;letleftLast=0,rightLast=right;while(left<right){constinPos=Math.floor((right+left)/2)constcompared=comparator(array[inPos],insertValue);if(compared<0){left=inPos;}elseif(compared>0){right=inPos;}else{right=inPos;left=inPos;}// nothing has changed, must have found limits. insert between.if(leftLast===left&&rightLast===right){break;}leftLast=left;rightLast=right;}// use right, because Math.floor is usedarray.splice(right,0,insertValue);returnarray}Knuth–Morris–Pratt algorithm implementation
functionDFA(s){leti=1letj=0constlen=s.lengthconstprefix=Array(len+1).fill(0)prefix[0]=-1prefix[1]=0while(i<len){if(s[j]===s[i]){j++i++prefix[i]=j}else{if(j>0)j=prefix[j]elsei++}}returnprefix}functionsearch(text,pattern){lett=0letp=0consttLen=text.lengthconstpLen=pattern.lengthconstmatches=[]constprefix=DFA(pattern)while(t<tLen){if(pattern[p]===text[t]){p++t++if(p===pLen){matches.push(t)p=prefix[p]}}else{p=prefix[p]if(p<0){t++p++}}}returnmatches}LeetCode-1392.Longest Happy Prefix
Binary Indexed Tree implementation
constlowBit=(x)=>x&-xclassFenwickTree{constructor(n){if(n<1)returnthis.sum=Array(n+1).fill(0)}update(i,delta){if(i<1)returnwhile(i<this.sum.length){this.sum[i]+=deltai+=lowBit(i)}}query(i){if(i<1)returnletsum=0while(i>0){sum+=this.sum[i]i-=lowBit(i)}returnsum}}LeetCode-307.Range Sum Query - Mutable
Segment Tree
classSegmentTree{/* Constructor to construct segment tree from given array. This constructor allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */constructor(arr,n){// Allocate memory for segment tree//Height of segment treeconstx=Math.ceil(Math.log(n)/Math.log(2))//Maximum size of segment treeconstmax_size=2*Math.pow(2,x)-1this.st=newArray(max_size)// Memory allocationthis.constructSTUtil(arr,0,n-1,0)}// A utility function to get the middle index from corner indexes.getMid(s,e){returns+(((e-s)/2)>>0)}/* A recursive function to get the sum of values in given range of the array. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[si] qs & qe --> Starting and ending indexes of query range */getSumUtil(ss,se,qs,qe,si){// If segment of this node is a part of given range, then return// the sum of the segmentif(qs<=ss&&qe>=se)returnthis.st[si]// If segment of this node is outside the given rangeif(se<qs||ss>qe)return0// If a part of this segment overlaps with the given rangeconstmid=this.getMid(ss,se)return(this.getSumUtil(ss,mid,qs,qe,2*si+1)+this.getSumUtil(mid+1,se,qs,qe,2*si+2))}/* A recursive function to update the nodes which have the given index in their range. The following are parameters st, si, ss and se are same as getSumUtil() i --> index of the element to be updated. This index is in input array. diff --> Value to be added to all nodes which have i in range */updateValueUtil(ss,se,i,diff,si){// Base Case: If the input index lies outside the range of// this segmentif(i<ss||i>se)return// If the input index is in range of this node, then update the// value of the node and its childrenthis.st[si]=this.st[si]+diffif(se!=ss){constmid=this.getMid(ss,se)this.updateValueUtil(ss,mid,i,diff,2*si+1)this.updateValueUtil(mid+1,se,i,diff,2*si+2)}}// The function to update a value in input array and segment tree.// It uses updateValueUtil() to update the value in segment treeupdateValue(arr,n,i,new_val){// Check for erroneous input indexif(i<0||i>n-1){return}// Get the difference between new value and old valueconstdiff=new_val-arr[i]// Update the value in arrayarr[i]=new_val// Update the values of nodes in segment treethis.updateValueUtil(0,n-1,i,diff,0)}// Return sum of elements in range from index qs (quey start) to// qe (query end). It mainly uses getSumUtil()getSum(n,qs,qe){// Check for erroneous input valuesif(qs<0||qe>n-1||qs>qe){return-1}returnthis.getSumUtil(0,n-1,qs,qe,0)}// A recursive function that constructs Segment Tree for array[ss..se].// si is index of current node in segment tree stconstructSTUtil(arr,ss,se,si){// If there is one element in array, store it in current node of// segment tree and returnif(ss==se){this.st[si]=arr[ss]returnarr[ss]}// If there are more than one elements, then recur for left and// right subtrees and store the sum of values in this nodeconstmid=this.getMid(ss,se)this.st[si]=this.constructSTUtil(arr,ss,mid,si*2+1)+this.constructSTUtil(arr,mid+1,se,si*2+2)returnthis.st[si]}}/**const arr = [1, 3, 5, 7, 9, 11]const n = arr.lengthconst t = new SegmentTree(arr, n)const log = console.loglog(t.getSum(n, 1, 3))t.updateValue(arr, n, 1, 10)log(t.getSum(n, 1, 3))*/Union-Find implementation
classUF{constructor(n){this.root=Array(n).fill(null).map((_,i)=>i)}find(x){if(this.root[x]!==x){this.root[x]=this.find(this.root[x])}returnthis.root[x]}union(x,y){constxr=this.find(x)constyr=this.find(y)this.root[yr]=xr}}// anotherclassUF{constructor(){this.root={}}find(x){if(this.root[x]!==x){this.root[x]=this.find(this.root[x])}returnthis.root[x]}union(x,y){if(this.root[x]==null)this.root[x]=xif(this.root[y]==null)this.root[y]=yconstxr=this.find(x)constyr=this.find(y)this.root[yr]=xr}getGroups(){constg={}for(const[u,_]ofObject.entries(this.root)){constr=this.find(u)if(g[r]==null)g[r]=[]g[r].push(u)}returng}}// anotherclassUnionFind{constructor(n){this.parents=Array(n).fill(0).map((e,i)=>i+1)this.ranks=Array(n).fill(0)}root(x){while(x!==this.parents[x]){this.parents[x]=this.parents[this.parents[x]]x=this.parents[x]}returnx}find(x){// if (x !== this.parents[x]) this.parents[x] = this.find(this.parents[x])// return this.parents[x]returnthis.root(x)}check(x,y){returnthis.root(x)===this.root(y)}union(x,y){const[rx,ry]=[this.find(x),this.find(y)]if(this.ranks[rx]>=this.ranks[ry]){this.parents[ry]=rxthis.ranks[rx]+=this.ranks[ry]}elseif(this.ranks[ry]>this.ranks[rx]){this.parents[rx]=rythis.ranks[ry]+=this.ranks[rx]}}}PriorityQueue implementation
classPriorityQueue{constructor(comparator=(a,b)=>a>b){this.heap=[]this.top=0this.comparator=comparator}size(){returnthis.heap.length}isEmpty(){returnthis.size()===0}peek(){returnthis.heap[this.top]}push(...values){values.forEach((value)=>{this.heap.push(value)this.siftUp()})returnthis.size()}pop(){constpoppedValue=this.peek()constbottom=this.size()-1if(bottom>this.top){this.swap(this.top,bottom)}this.heap.pop()this.siftDown()returnpoppedValue}replace(value){constreplacedValue=this.peek()this.heap[this.top]=valuethis.siftDown()returnreplacedValue}parent=(i)=>((i+1)>>>1)-1left=(i)=>(i<<1)+1right=(i)=>(i+1)<<1greater=(i,j)=>this.comparator(this.heap[i],this.heap[j])swap=(i,j)=>([this.heap[i],this.heap[j]]=[this.heap[j],this.heap[i]])siftUp=()=>{letnode=this.size()-1while(node>this.top&&this.greater(node,this.parent(node))){this.swap(node,this.parent(node))node=this.parent(node)}}siftDown=()=>{letnode=this.topwhile((this.left(node)<this.size()&&this.greater(this.left(node),node))||(this.right(node)<this.size()&&this.greater(this.right(node),node))){letmaxChild=this.right(node)<this.size()&&this.greater(this.right(node),this.left(node))
? this.right(node)
: this.left(node)this.swap(node,maxChild)node=maxChild}}}Quicksort implementation
functionquickSort(arr){// your code heresort(arr,0,arr.length-1)}functionsort(arr,start,end){if(start>=end)returnconstpivot=partition(arr,start,end)sort(arr,start,pivot-1)sort(arr,pivot+1,end)}functionpartition(arr,start,end){constmid=arr[start]letl=start+1,r=endwhile(l<=r){if(arr[l]<=mid)l++else{swap(arr,l,r)r--}}swap(arr,start,r)returnr}functionswap(arr,i,j){;[arr[i],arr[j]]=[arr[j],arr[i]]}Quicksort implementation
functionQuickSelect(array,k,comparator){constcompare=comparator||defaultcomparator;if(array.length<k){returnarray;}constidx=select(array,k,compare);if(idx!==k)console.log("could not complete quickselect");returnarray;}constdefaultcomparator=(a,b)=>a<b;functionswap(array,index1,index2){consttemp=array[index1];array[index1]=array[index2];array[index2]=temp;}functionpartition(array,leftindex,rightindex,pivotindex,compare){constpivotvalue=array[pivotindex];swap(array,pivotindex,rightindex);letstoreindex=leftindex;for(leti=leftindex;i<rightindex;i+=1){if(compare(array[i],pivotvalue)){swap(array,storeindex,i);storeindex+=1;}}swap(array,rightindex,storeindex);returnstoreindex;}functionselect(array,k,compare){letleftindex=0;letrightindex=array.length-1;while(true){if(leftindex==rightindex)returnleftindex;letpivotindex=leftindex+Math.floor((rightindex-leftindex)/2);pivotindex=partition(array,leftindex,rightindex,pivotindex,compare);if(k===pivotindex)returnk;if(k<pivotindex)rightindex=pivotindex-1;elseleftindex=pivotindex+1;}}Mergesort implementation
/** * @param {number[]} arr */functionmergeSort(arr){// your code hereif(arr.length<2)returnconstmid=Math.floor(arr.length/2)constleft=arr.slice(0,mid)constright=arr.slice(mid)mergeSort(left)mergeSort(right)letl=0,r=0while(l<left.length||r<right.length){if(r===right.length||(l<left.length&&left[l]<=right[r])){arr[l+r]=left[l++]}else{arr[l+r]=right[r++]}}}// Merges two subarrays of arr[].// First subarray is arr[l..m]// Second subarray is arr[m+1..r]functionmerge(arr,l,m,r){leti,j,kconstn1=m-l+1constn2=r-m/* create temp arrays */constL=Array(n1).fill(0)constR=Array(n2).fill(0)/* Copy data to temp arrays L[] and R[] */for(i=0;i<n1;i++)L[i]=arr[l+i]for(j=0;j<n2;j++)R[j]=arr[m+1+j]/* Merge the temp arrays back into arr[l..r]*/i=0// Initial index of first subarrayj=0// Initial index of second subarrayk=l// Initial index of merged subarraywhile(i<n1&&j<n2){if(L[i]<=R[j]){arr[k]=L[i]i++}else{arr[k]=R[j]j++}k++}/* Copy the remaining elements of L[], if there are any */while(i<n1){arr[k]=L[i]i++k++}/* Copy the remaining elements of R[], if there are any */while(j<n2){arr[k]=R[j]j++k++}}/* l is for left index and r is right index of the sub-array of arr to be sorted */functionmergeSort(arr,l,r){if(l<r){// Same as (l+r)/2, but avoids overflow for// large l and hconstm=l+((r-l)>>1)// Sort first and second halvesmergeSort(arr,l,m)mergeSort(arr,m+1,r)merge(arr,l,m,r)}}LeetCode-315. Count of Smaller Numbers After Self
LeetCode-327. Count of Range Sum
BinarySearch implementation
/** * @param {number[]} nums * @param {number} target * @return {number} */constBinarySearch=function(nums,target){constn=nums.lengthletl=0,r=n-1while(l<=r){constmid=l+((r-l)>>1)if(nums[mid]===target)returnmidif(nums[mid]>target)r=mid-1elsel=mid+1}returnl};/**Why return low rather than high?The last iteration is lo == hi == midWhen target > nums[mid] == nums[lo] == nums[hi], after loop lo = lo + 1 == high +1 which will be the correct index for insertionWhen target < nums[mid] == nums[lo] == nums[hi], after loop hi = hi - 1 == low - 1 is not the correct index, should be lowWhy does Binary search algorithm use floor and not ceiling - not in an half open range?This all depends on how you update your left and right variable.Normally, we use left = middle+1 and right = middle-1, with stopping criteria left = right.In this case, ceiling or flooring the middle value doesn't matter.However, if we use left = middle+1 and right = middle, we must take the floor of the middle value, otherwise we end up in an endless loop.Consider finding 11 in array 11, 22.We set left = 0 and right = 1, the middle is 0.5, if we take the ceiling, it would be 1.Since 22 is larger than query, we need to cut the right half and move right boarder towards middle.This works fine when the array is large, but since there are only two elements.right = middle will again set right to 1. We have an infinite loop.To sum up,both ceiling and flooring work fine with left = middle+1 and right = middle-1ceiling works fine with left = middle and right = middle-1flooring works fine with left = middle+1 and right = middle*/functionbinarySearch(arr,compareFn,target){letleft=0;// inclusiveletright=arr.length;// exclusiveletfound;while(left<right){constmiddle=left+((right-left)>>1);constcompareResult=compareFn(target,arr[middle]);if(compareResult>0){left=middle+1;}else{right=middle;// We are looking for the lowest index so we can't return immediately.found=!compareResult;}}// left is the index if found, or the insertion point otherwise.// ~left is a shorthand for -left - 1.returnfound ? left : ~left;};Greatest common divisor implementation
functionGCD(a,b){if(a===0)returnbif(b===0)returnareturnGCD(Math.abs(a-b),Math.min(a,b))}// orfunctiongcd(a,b){returnb ? gcd(b,a%b) : a}// orfunctiongcd(a,b){while(b){a%=bb=[a,(a=b)][0]}returna}Least Common Multiple implementation
functionlcm(a,b){returna/gcd(a,b)*b;}// anotherfunctionlcm(a,b){returna*b/gcd(a,b);}Manacher's Algorithm implementation
functionmanachersAlgorithm(s,N){conststr=getModifiedString(s,N)constlen=2*N+1// expansion lengthconstP=newArray(len).fill(0)// stores the center of the longest palindromic substring until nowletc=0// stores the right boundary of the longest palindromic substring until nowletr=0letmaxLen=0for(leti=0;i<len;i++){//get mirror index of iconstmirror=2*c-i// see if the mirror of i is expanding beyond the left boundary// of current longest palindrome at center c// if it is, then take r - i as P[i]// else take P[mirror] as P[i]if(i<r){P[i]=Math.min(r-i,P[mirror])}//expand at ileta=i+(1+P[i])letb=i-(1+P[i])while(a<len&&b>=0&&str.charAt(a)===str.charAt(b)){P[i]++a++b--}// check if the expanded palindrome at i is expanding beyond the// right boundary of current longest palindrome at center c// if it is, the new center is iif(i+P[i]>r){c=ir=i+P[i]if(P[i]>maxLen){maxLen=P[i]}}}returnmaxLen}functiongetModifiedString(s,N){letsb=''for(leti=0;i<N;i++){sb+='#'sb+=s.charAt(i)}sb+='#'returnsb}Gray code implementation
functionBinaryToGray(num){// The operator >> is shift right. The operator ^ is exclusive or.returnnum^(num>>1);}// This function converts a reflected binary Gray code number to a binary number.functionGrayToBinary(num){letmask=num;// Each Gray code bit is exclusive-ored with all more significant bits.while(mask){mask>>=1;num^=mask;}returnnum;}// A more efficient version for Gray codes 32 bits or fewer// through the use of SWAR (SIMD within a register) techniques. // It implements a parallel prefix XOR function. The assignment// statements can be in any order.// // This function can be adapted for longer Gray codes by adding steps. functionGrayToBinary32(num){num^=num>>16;num^=num>>8;num^=num>>4;num^=num>>2;num^=num>>1;returnnum;}Trie implementation
classTrieNode{constructor(v,isComplete=false){this.val=v;this.isComplete=isComplete;this.children=newMap();}}classTrie{constructor(){this.head=newTrieNode(null);}/** * @param {string} word * @return {Trie} */addWord(word){constcharacters=Array.from(word);letcurrentNode=this.head;for(letcharIndex=0;charIndex<characters.length;charIndex++){constisComplete=charIndex===characters.length-1;constchar=characters[charIndex];if(currentNode.children.has(char)){currentNode=currentNode.children.get(char);}else{constchild=newTrieNode(char,isComplete);currentNode.children.set(char,child);currentNode=child;}}returnthis;}/** * @param {string} word * @return {Trie} */deleteWord(word){constdepthFirstDelete=(currentNode,charIndex=0)=>{if(charIndex>=word.length){return;}constcharacter=word[charIndex];constnextNode=currentNode.children.get(character);if(nextNode==null){return;}depthFirstDelete(nextNode,charIndex+1);if(charIndex===word.length-1){nextNode.isComplete=false;}// childNode is deleted only if:// - childNode has NO children// - childNode.isComplete === falseif(nextNode.children.size===0){currentNode.children.delete(character);}};depthFirstDelete(this.head);returnthis;}/** * @param {string} word * @return {string[]} */suggestNextCharacters(word){constlastCharacter=this.getLastCharacterNode(word);if(!lastCharacter){returnnull;}returnthis.suggestChildren(lastCharacter);}/** * @param {TrieNode} node * @return {TrieNode} */suggestChildren(node){if(node==null)return[];return[...node.children.keys()];}/** * Check if complete word exists in Trie. * * @param {string} word * @return {boolean} */doesWordExist(word){constlastCharacter=this.getLastCharacterNode(word);return!!lastCharacter&&lastCharacter.isComplete;}/** * @param {string} word * @return {TrieNode} */getLastCharacterNode(word){constcharacters=Array.from(word);letcurrentNode=this.head;for(letcharIndex=0;charIndex<characters.length;charIndex++){constchar=characters[charIndex];if(!currentNode.children.has(char)){returnnull;}currentNode=currentNode.children.get(char);}returncurrentNode;}}Bloom filter implementation
classBloomFilter{/** * @param {number} size - the size of the storage. */constructor(size=100){// Bloom filter size directly affects the likelihood of false positives.// The bigger the size the lower the likelihood of false positives.this.size=sizethis.storage=this.createStore(size)}/** * @param {string} item */insert(item){consthashValues=this.getHashValues(item)hashValues.forEach((val)=>this.storage.setValue(val))}/** * @param {string} item * @return {boolean} */mayContain(item){consthashValues=this.getHashValues(item)for(lethashIndex=0;hashIndex<hashValues.length;hashIndex+=1){if(!this.storage.getValue(hashValues[hashIndex])){returnfalse}}returntrue}/** * @param {number} size * @return {Object} */createStore(size){conststorage=[]for(letstorageCellIndex=0;storageCellIndex<size;storageCellIndex+=1){storage.push(false)}conststorageInterface={getValue(index){returnstorage[index]},setValue(index){storage[index]=true},}returnstorageInterface}/** * @param {string} item * @return {number} */hash1(item){lethash=0for(letcharIndex=0;charIndex<item.length;charIndex+=1){constchar=item.charCodeAt(charIndex)hash=(hash<<5)+hash+charhash&=hashhash=Math.abs(hash)}returnhash%this.size}/** * @param {string} item * @return {number} */hash2(item){lethash=5381for(letcharIndex=0;charIndex<item.length;charIndex+=1){constchar=item.charCodeAt(charIndex)hash=(hash<<5)+hash+char}returnMath.abs(hash%this.size)}/** * @param {string} item * @return {number} */hash3(item){lethash=0for(letcharIndex=0;charIndex<item.length;charIndex+=1){constchar=item.charCodeAt(charIndex)hash=(hash<<5)-hashhash+=charhash&=hash}returnMath.abs(hash%this.size)}/** * Runs all 3 hash functions on the input and returns an array of results. * * @param {string} item * @return {number[]} */getHashValues(item){return[this.hash1(item),this.hash2(item),this.hash3(item)]}}Inverse element implementation
functioninverseElement(a,n){letN=nif(GCD(a,n)==1){letp=1,q=0,r=0,s=1letc,quot,new_r,new_swhile(n!==0){c=modulo(a,n)quot=Math.floor(a/n)a=nn=cnew_r=p-quot*rnew_s=q-quot*sp=rq=sr=new_rs=new_s}returnmodulo(p,N)}else{returnnull}}functionmodulo(a,n){if(a>=0){returna%n}else{return(a%n)+n}}// anotherfunctioninverseElement(a,b){returnquickPow(a,b-2)%b}functionquickPow(a,b){letans=1;a=(a%p+p)%p;for(;b;b>>=1){if(b&1)ans=(a*ans)%p;a=(a*a)%p;}returnans;}Sieve of Eratosthenes implementation
/** * @param {number} maxNumber * @return {number[]} */exportdefaultfunctionsieveOfEratosthenes(maxNumber){constisPrime=newArray(maxNumber+1).fill(true);isPrime[0]=false;isPrime[1]=false;constprimes=[];for(letnumber=2;number<=maxNumber;number+=1){if(isPrime[number]===true){primes.push(number);letnextNumber=number*2;while(nextNumber<=maxNumber){isPrime[nextNumber]=false;nextNumber+=number;}}}returnprimes;}Square root implementation
functionsquareRoot(number,tolerance=0.0001){if(number<0){returnnull;}if(number===0){return0;}letroot=1;constrequiredDelta=1/(10**tolerance);while(Math.abs(number-(root**2))>requiredDelta){root-=((root**2)-number)/(2*root);}returnMath.round(root*(10**tolerance))/(10**tolerance);}Is power of two implementation
functionisPowerOfTwoBitwise(number){if(number<1)returnfalsereturn(number&(number-1))===0;}Integer partition implementation
functionintegerPartition(number){constpartitionMatrix=Array(number+1).fill(null).map(()=>{returnArray(number+1).fill(null)})for(letnumberIndex=1;numberIndex<=number;numberIndex++){partitionMatrix[0][numberIndex]=0}for(letsummandIndex=0;summandIndex<=number;summandIndex++){partitionMatrix[summandIndex][0]=1}for(letsummandIndex=1;summandIndex<=number;summandIndex++){for(letnumberIndex=1;numberIndex<=number;numberIndex++){if(summandIndex>numberIndex){partitionMatrix[summandIndex][numberIndex]=partitionMatrix[summandIndex-1][numberIndex]}else{constcombosWithoutSummand=partitionMatrix[summandIndex-1][numberIndex]constcombosWithSummand=partitionMatrix[summandIndex][numberIndex-summandIndex]partitionMatrix[summandIndex][numberIndex]=combosWithoutSummand+combosWithSummand}}}returnpartitionMatrix[number][number]}Power implementation
functionpower(base,power){if(power===0)return1if(power%2===0){constmultiplier=fastPowering(base,power/2)returnmultiplier*multiplier}constmultiplier=fastPowering(base,Math.floor(power/2))returnmultiplier*multiplier*base}Combinations implementation
// combinations without repetitionfunctioncomb(n,r){if(n<r)return0;letres=1;if(n-r<r)r=n-r;for(leti=n,j=1;i>=1&&j<=r;--i,++j){res=res*i;}for(leti=r;i>=2;--i){res=res/i;}returnres;}Bell number implementation
// Bell triangle methodfunctionbellNumber(n){constbell=Array.from({length: n+1},()=>Array(n+1).fill(0))bell[0][0]=1for(leti=1;i<=n;i++){bell[i][0]=bell[i-1][i-1]for(letj=1;j<=i;j++)bell[i][j]=bell[i-1][j-1]+bell[i][j-1]}returnbell[n][0]}Partition a set into k subsets implementation
// Returns count of different partitions of n// elements in k subsetsfunctioncountP(n,k){constdp=Array.from({length: n+1},()=>Array(k+1).fill(0))// Base casesfor(leti=0;i<=n;i++)dp[i][0]=0for(leti=0;i<=k;i++)dp[0][k]=0// Bottom upfor(leti=1;i<=n;i++){for(letj=1;j<=k;j++){if(j==1||i==j)dp[i][j]=1elsedp[i][j]=j*dp[i-1][j]+dp[i-1][j-1]}}returndp[n][k]}TreeSet implementation
classTreeSet{constructor(comparator){this.length=0this.elements=[]if(comparator)this.comparator=comparatorelsethis.comparator=(a,b)=>a>b ? 1 : (a<b ? -1 : 0)}size(){returnthis.elements.length}last(){returnthis.elements[this.length-1]}first(){returnthis.elements[0]}isEmpty(){returnthis.size()===0}pollLast(){if(this.length>0){this.length--returnthis.elements.splice(this.length,1)}returnnull}pollFirst(){if(this.length>0){this.length--returnthis.elements.splice(0,1)}returnnull}add(element){letindex=this.binarySearch(element)if(index>=0)returnindex=-index-1this.elements.splice(index,0,element)this.length++}/** * Performs a binary search of value in array * @param {number[]} array - Array in which value will be searched. It must be sorted. * @param {number} value - Value to search in array * @return {number} If value is found, returns its index in array. Otherwise, returns * a negative number indicating where the value should be inserted: -(index + 1) */binarySearch(value){letlow=0lethigh=this.elements.length-1while(low<=high){letmid=low+((high-low)>>>1)letmidValue=this.elements[mid]letcmp=this.comparator(midValue,value)if(cmp<0)low=mid+1elseif(cmp>0)high=mid-1elsereturnmid}return-(low+1)}}Red black tree implementation
classComparator{constructor(compareFunction){this.compare=compareFunction||Comparator.defaultCompareFunction}staticdefaultCompareFunction(a,b){if(a===b){return0}returna<b ? -1 : 1}equal(a,b){returnthis.compare(a,b)===0}lessThan(a,b){returnthis.compare(a,b)<0}greaterThan(a,b){returnthis.compare(a,b)>0}lessThanOrEqual(a,b){returnthis.lessThan(a,b)||this.equal(a,b)}greaterThanOrEqual(a,b){returnthis.greaterThan(a,b)||this.equal(a,b)}reverse(){constcompareOriginal=this.comparethis.compare=(a,b)=>compareOriginal(b,a)}}classLinkedListNode{constructor(value,next=null){this.value=valuethis.next=next}toString(callback){returncallback ? callback(this.value) : `${this.value}`}}classLinkedList{constructor(comparatorFunction){this.head=nullthis.tail=nullthis.compare=newComparator(comparatorFunction)}prepend(value){constnewNode=newLinkedListNode(value,this.head)this.head=newNodeif(!this.tail){this.tail=newNode}returnthis}append(value){constnewNode=newLinkedListNode(value)if(!this.head){this.head=newNodethis.tail=newNodereturnthis}this.tail.next=newNodethis.tail=newNodereturnthis}delete(value){if(!this.head){returnnull}letdeletedNode=nullwhile(this.head&&this.compare.equal(this.head.value,value)){deletedNode=this.headthis.head=this.head.next}letcurrentNode=this.headif(currentNode!==null){while(currentNode.next){if(this.compare.equal(currentNode.next.value,value)){deletedNode=currentNode.nextcurrentNode.next=currentNode.next.next}else{currentNode=currentNode.next}}}if(this.compare.equal(this.tail.value,value)){this.tail=currentNode}returndeletedNode}find({ value =undefined, callback =undefined}){if(!this.head){returnnull}letcurrentNode=this.headwhile(currentNode){if(callback&&callback(currentNode.value)){returncurrentNode}if(value!==undefined&&this.compare.equal(currentNode.value,value)){returncurrentNode}currentNode=currentNode.next}returnnull}deleteTail(){constdeletedTail=this.tailif(this.head===this.tail){this.head=nullthis.tail=nullreturndeletedTail}letcurrentNode=this.headwhile(currentNode.next){if(!currentNode.next.next){currentNode.next=null}else{currentNode=currentNode.next}}this.tail=currentNodereturndeletedTail}deleteHead(){if(!this.head){returnnull}constdeletedHead=this.headif(this.head.next){this.head=this.head.next}else{this.head=nullthis.tail=null}returndeletedHead}fromArray(values){values.forEach((value)=>this.append(value))returnthis}toArray(){constnodes=[]letcurrentNode=this.headwhile(currentNode){nodes.push(currentNode)currentNode=currentNode.next}returnnodes}toString(callback){returnthis.toArray().map((node)=>node.toString(callback)).toString()}reverse(){letcurrNode=this.headletprevNode=nullletnextNode=nullwhile(currNode){nextNode=currNode.nextcurrNode.next=prevNodeprevNode=currNodecurrNode=nextNode}this.tail=this.headthis.head=prevNodereturnthis}}constdefaultHashTableSize=32classHashTable{constructor(hashTableSize=defaultHashTableSize){this.buckets=Array(hashTableSize).fill(null).map(()=>newLinkedList())this.keys={}}hash(key){consthash=Array.from(key).reduce((hashAccumulator,keySymbol)=>hashAccumulator+keySymbol.charCodeAt(0),0)returnhash%this.buckets.length}set(key,value){constkeyHash=this.hash(key)this.keys[key]=keyHashconstbucketLinkedList=this.buckets[keyHash]constnode=bucketLinkedList.find({callback: (nodeValue)=>nodeValue.key===key,})if(!node){bucketLinkedList.append({ key, value })}else{node.value.value=value}}delete(key){constkeyHash=this.hash(key)deletethis.keys[key]constbucketLinkedList=this.buckets[keyHash]constnode=bucketLinkedList.find({callback: (nodeValue)=>nodeValue.key===key,})if(node){returnbucketLinkedList.delete(node.value)}returnnull}get(key){constbucketLinkedList=this.buckets[this.hash(key)]constnode=bucketLinkedList.find({callback: (nodeValue)=>nodeValue.key===key,})returnnode ? node.value.value : undefined}has(key){returnObject.hasOwnProperty.call(this.keys,key)}getKeys(){returnObject.keys(this.keys)}}classBinaryTreeNode{constructor(value=null){this.left=nullthis.right=nullthis.parent=nullthis.value=valuethis.meta=newHashTable()this.nodeComparator=newComparator()}getleftHeight(){if(!this.left){return0}returnthis.left.height+1}getrightHeight(){if(!this.right){return0}returnthis.right.height+1}getheight(){returnMath.max(this.leftHeight,this.rightHeight)}getbalanceFactor(){returnthis.leftHeight-this.rightHeight}getuncle(){if(!this.parent){returnundefined}if(!this.parent.parent){returnundefined}if(!this.parent.parent.left||!this.parent.parent.right){returnundefined}if(this.nodeComparator.equal(this.parent,this.parent.parent.left)){returnthis.parent.parent.right}returnthis.parent.parent.left}setValue(value){this.value=valuereturnthis}setLeft(node){if(this.left){this.left.parent=null}this.left=nodeif(this.left){this.left.parent=this}returnthis}setRight(node){if(this.right){this.right.parent=null}this.right=nodeif(node){this.right.parent=this}returnthis}removeChild(nodeToRemove){if(this.left&&this.nodeComparator.equal(this.left,nodeToRemove)){this.left=nullreturntrue}if(this.right&&this.nodeComparator.equal(this.right,nodeToRemove)){this.right=nullreturntrue}returnfalse}replaceChild(nodeToReplace,replacementNode){if(!nodeToReplace||!replacementNode){returnfalse}if(this.left&&this.nodeComparator.equal(this.left,nodeToReplace)){this.left=replacementNodereturntrue}if(this.right&&this.nodeComparator.equal(this.right,nodeToReplace)){this.right=replacementNodereturntrue}returnfalse}staticcopyNode(sourceNode,targetNode){targetNode.setValue(sourceNode.value)targetNode.setLeft(sourceNode.left)targetNode.setRight(sourceNode.right)}traverseInOrder(){lettraverse=[]if(this.left){traverse=traverse.concat(this.left.traverseInOrder())}traverse.push(this.value)if(this.right){traverse=traverse.concat(this.right.traverseInOrder())}returntraverse}toString(){returnthis.traverseInOrder().toString()}}classBinarySearchTreeNodeextendsBinaryTreeNode{constructor(value=null,compareFunction=undefined){super(value)this.compareFunction=compareFunctionthis.nodeValueComparator=newComparator(compareFunction)}insert(value){if(this.nodeValueComparator.equal(this.value,null)){this.value=valuereturnthis}if(this.nodeValueComparator.lessThan(value,this.value)){if(this.left){returnthis.left.insert(value)}constnewNode=newBinarySearchTreeNode(value,this.compareFunction)this.setLeft(newNode)returnnewNode}if(this.nodeValueComparator.greaterThan(value,this.value)){if(this.right){returnthis.right.insert(value)}constnewNode=newBinarySearchTreeNode(value,this.compareFunction)this.setRight(newNode)returnnewNode}returnthis}find(value){if(this.nodeValueComparator.equal(this.value,value)){returnthis}if(this.nodeValueComparator.lessThan(value,this.value)&&this.left){returnthis.left.find(value)}if(this.nodeValueComparator.greaterThan(value,this.value)&&this.right){returnthis.right.find(value)}returnnull}contains(value){return!!this.find(value)}remove(value){constnodeToRemove=this.find(value)if(!nodeToRemove){thrownewError('Item not found in the tree')}const{ parent }=nodeToRemoveif(!nodeToRemove.left&&!nodeToRemove.right){if(parent){parent.removeChild(nodeToRemove)}else{nodeToRemove.setValue(undefined)}}elseif(nodeToRemove.left&&nodeToRemove.right){constnextBiggerNode=nodeToRemove.right.findMin()if(!this.nodeComparator.equal(nextBiggerNode,nodeToRemove.right)){this.remove(nextBiggerNode.value)nodeToRemove.setValue(nextBiggerNode.value)}else{nodeToRemove.setValue(nodeToRemove.right.value)nodeToRemove.setRight(nodeToRemove.right.right)}}else{constchildNode=nodeToRemove.left||nodeToRemove.rightif(parent){parent.replaceChild(nodeToRemove,childNode)}else{BinaryTreeNode.copyNode(childNode,nodeToRemove)}}nodeToRemove.parent=nullreturntrue}findMin(){if(!this.left){returnthis}returnthis.left.findMin()}}classBinarySearchTree{constructor(nodeValueCompareFunction){this.root=newBinarySearchTreeNode(null,nodeValueCompareFunction);this.nodeComparator=this.root.nodeComparator;}insert(value){returnthis.root.insert(value);}contains(value){returnthis.root.contains(value);}remove(value){returnthis.root.remove(value);}toString(){returnthis.root.toString();}}constRED_BLACK_TREE_COLORS={red: 'red',black: 'black',}constCOLOR_PROP_NAME='color'classRedBlackTreeextendsBinarySearchTree{insert(value){constinsertedNode=super.insert(value)if(this.nodeComparator.equal(insertedNode,this.root)){this.makeNodeBlack(insertedNode)}else{this.makeNodeRed(insertedNode)}this.balance(insertedNode)returninsertedNode}remove(value){thrownewError(`Can't remove ${value}. Remove method is not implemented yet`)}balance(node){if(this.nodeComparator.equal(node,this.root)){return}if(this.isNodeBlack(node.parent)){return}constgrandParent=node.parent.parentif(node.uncle&&this.isNodeRed(node.uncle)){this.makeNodeBlack(node.uncle)this.makeNodeBlack(node.parent)if(!this.nodeComparator.equal(grandParent,this.root)){this.makeNodeRed(grandParent)}else{return}this.balance(grandParent)}elseif(!node.uncle||this.isNodeBlack(node.uncle)){if(grandParent){letnewGrandParentif(this.nodeComparator.equal(grandParent.left,node.parent)){if(this.nodeComparator.equal(node.parent.left,node)){newGrandParent=this.leftLeftRotation(grandParent)}else{newGrandParent=this.leftRightRotation(grandParent)}}else{if(this.nodeComparator.equal(node.parent.right,node)){newGrandParent=this.rightRightRotation(grandParent)}else{newGrandParent=this.rightLeftRotation(grandParent)}}if(newGrandParent&&newGrandParent.parent===null){this.root=newGrandParentthis.makeNodeBlack(this.root)}this.balance(newGrandParent)}}}leftLeftRotation(grandParentNode){constgrandGrandParent=grandParentNode.parentletgrandParentNodeIsLeftif(grandGrandParent){grandParentNodeIsLeft=this.nodeComparator.equal(grandGrandParent.left,grandParentNode)}constparentNode=grandParentNode.leftconstparentRightNode=parentNode.rightparentNode.setRight(grandParentNode)grandParentNode.setLeft(parentRightNode)if(grandGrandParent){if(grandParentNodeIsLeft){grandGrandParent.setLeft(parentNode)}else{grandGrandParent.setRight(parentNode)}}else{parentNode.parent=null}this.swapNodeColors(parentNode,grandParentNode)returnparentNode}leftRightRotation(grandParentNode){constparentNode=grandParentNode.leftconstchildNode=parentNode.rightconstchildLeftNode=childNode.leftchildNode.setLeft(parentNode)parentNode.setRight(childLeftNode)grandParentNode.setLeft(childNode)returnthis.leftLeftRotation(grandParentNode)}rightRightRotation(grandParentNode){constgrandGrandParent=grandParentNode.parentletgrandParentNodeIsLeftif(grandGrandParent){grandParentNodeIsLeft=this.nodeComparator.equal(grandGrandParent.left,grandParentNode)}constparentNode=grandParentNode.rightconstparentLeftNode=parentNode.leftparentNode.setLeft(grandParentNode)grandParentNode.setRight(parentLeftNode)if(grandGrandParent){if(grandParentNodeIsLeft){grandGrandParent.setLeft(parentNode)}else{grandGrandParent.setRight(parentNode)}}else{parentNode.parent=null}this.swapNodeColors(parentNode,grandParentNode)returnparentNode}rightLeftRotation(grandParentNode){constparentNode=grandParentNode.rightconstchildNode=parentNode.leftconstchildRightNode=childNode.rightchildNode.setRight(parentNode)parentNode.setLeft(childRightNode)grandParentNode.setRight(childNode)returnthis.rightRightRotation(grandParentNode)}makeNodeRed(node){node.meta.set(COLOR_PROP_NAME,RED_BLACK_TREE_COLORS.red)returnnode}makeNodeBlack(node){node.meta.set(COLOR_PROP_NAME,RED_BLACK_TREE_COLORS.black)returnnode}isNodeRed(node){returnnode.meta.get(COLOR_PROP_NAME)===RED_BLACK_TREE_COLORS.red}isNodeBlack(node){returnnode.meta.get(COLOR_PROP_NAME)===RED_BLACK_TREE_COLORS.black}isNodeColored(node){returnthis.isNodeRed(node)||this.isNodeBlack(node)}swapNodeColors(firstNode,secondNode){constfirstColor=firstNode.meta.get(COLOR_PROP_NAME)constsecondColor=secondNode.meta.get(COLOR_PROP_NAME)firstNode.meta.set(COLOR_PROP_NAME,secondColor)secondNode.meta.set(COLOR_PROP_NAME,firstColor)}}TreeMap implementation
///////////////////////////////////////////////////// Template /////////////////////////////////////////////////////////////////functionBisect(){return{ insort_right, insort_left, bisect_left, bisect_right }functioninsort_right(a,x,lo=0,hi=null){lo=bisect_right(a,x,lo,hi);a.splice(lo,0,x);}functionbisect_right(a,x,lo=0,hi=null){// > upper_boundif(lo<0)thrownewError('lo must be non-negative');if(hi==null)hi=a.length;while(lo<hi){letmid=parseInt((lo+hi)/2);a[mid]>x ? hi=mid : lo=mid+1;}returnlo;}functioninsort_left(a,x,lo=0,hi=null){lo=bisect_left(a,x,lo,hi);a.splice(lo,0,x);}functionbisect_left(a,x,lo=0,hi=null){// >= lower_boundif(lo<0)thrownewError('lo must be non-negative');if(hi==null)hi=a.length;while(lo<hi){letmid=parseInt((lo+hi)/2);a[mid]<x ? lo=mid+1 : hi=mid;}returnlo;}}/*usage:let ts = new TreeMap();let ts = new TreeMap([[3, 1], [7, 1], [7, 2], [1, 1], [3, 2]]); // Map { 1 => 1, 3 => 2, 7 => 2 } (console.log(ts.show()))*/functionTreeMap(g){letts=[],m=newMap(),bisect=newBisect();initialize();return{ put, ceilingKey, higherKey, lowerKey, floorKey, ceilingEntry, higherEntry, lowerEntry, floorEntry, remove, contains, size, clear, show };functioninitialize(){if(g){for(const[k,v]ofg){if(!m.has(k))bisect.insort_right(ts,k);m.set(k,v);}}}functionput(k,v){if(!m.has(k))bisect.insort_right(ts,k);// ts has no duplicates/unique keym.set(k,v);// update key with most recent value}functionceilingKey(e){// >= lower_boundletidx=bisect.bisect_right(ts,e);letres=ts[idx-1]==e ? e : ts[bisect.bisect_right(ts,e)];returnres==undefined ? null : res;}functionhigherKey(e){// > upper_boundletidx=bisect.bisect_right(ts,e);letres=ts[idx]>e ? ts[idx] : ts[bisect.bisect_right(ts,e)+1];returnres==undefined ? null : res;}functionfloorKey(e){// <= letidx=bisect.bisect_left(ts,e);letres=ts[idx]==e ? e : ts[bisect.bisect_left(ts,e)-1];returnres==undefined ? null : res;}functionlowerKey(e){// <letidx=bisect.bisect_left(ts,e);letres=ts[idx]<e ? ts[idx] : ts[bisect.bisect_left(ts,e)-1];returnres==undefined ? null : res;}functiondata(k){returnk==null ? null : {key: k,value: m.get(k)}}functionceilingEntry(k){returndata(ceilingKey(k));}functionhigherEntry(k){returndata(higherKey(k));}functionfloorEntry(k){returndata(floorKey(k));}functionlowerEntry(k){returndata(lowerKey(k));}functionremove(e){letidx=bisect.bisect_left(ts,e);if(ts[idx]==e)ts.splice(idx,1);m.delete(e);}functioncontains(e){returnm.has(e);}functionsize(){returnts.length;}functionclear(){ts=[];m.clear();}functionshow(){letres=newMap();for(constxofts)res.set(x,m.get(x));returnres;}}//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////