trekhleb/javascript-algorithms

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings

javascript-algorithms's Issues

Implementing Segment tree

I'm planning to get started on a segment tree implementation. The first step would be to implement Range Min Query, then possibly a generalized implementation.

Quick sort should not allocate extra memory like left / right array.

wiki: https://en.wikipedia.org/wiki/Quicksort

Is Radix Sort an advanced Algorithm?

Shouldn't it be classified as "Beginner"?

Big O Notation?

I'm thinking of adding Big O notation to the docs based on Big-O Cheat Sheet. Would this be useful?

AVL tree does not rebalance after removal

Hi! Thanks for your project. I can't seem to find the removal algorithm in AVL tree: if it simply borrows the binary tree removal, it's incomplete. I was particularly interested in that, cause I have been looking for a removal procedure that doesn't mutate the nodes.

Cheers.

Translation

Hello, Can I try to translate the repo to Chinese?

automated test suite

a suggestion for improve quality, readability and robustness of the algorithms is to have test cases.

without tests it is hard to know if the algorithms / data structure works as intended.

Grouping algorithms for studying

Thank you for creating this repo, it's awesome.
I just have one small question, can you divide all algorithms into group of level like: Beginner, Intermediate, Advance , etc so someone like students or newbies know where to start?

Translate to russian

Hello.

I want to translate all README into Russian, are there any rules for translation?

Add doubly linked list

Shouldn't there be doubly linked list too?

If yes, can I contribute for it?

Collision resolution in hash-table

In the HashTable implementation currently there is no collision resolution mechanism. The following insertion method updates the existing node. There can be chaining or open addressing methods implemented.

  insert(key, value) {
    const bucketLinkedList = this.buckets[this.hash(key)];
    const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key });

    if (!node) {
      // Insert new node.
      bucketLinkedList.append({ key, value });
    } else {
      // Update value of existing node.
      node.value.value = value;
    }
  }  

rabinKarp seems to miss some matches

Hello,

I recently tried to run some property based tests on the algorithms provided in javascript-algorithms.
I discovered the following failing case with rabinKarp algorithm:

expect(rabinKarp("^ !/'#'pp", " !/'#'pp")).toBe(2); // output: -1

In order to find it, I used fast-check framework with the property:

// for any strings a, b and c
// rabinKarp(a + b + c, b) should be different from -1 (indeed b is a substring of a+b+c)
fc.assert(
  fc.property(
    fc.string(), fc.string(), fc.string(),
    (a, b, c) => rabinKarp(a + b + c, b) !== -1
  )
);

I was not able to have a smaller example for this precise case :/

Fix errors in grammar and descriptions in README.md

This file contains some grammatical errors and could use better sentence arrangements

knapsack item settings ignores itemsInStock

the algorithm ignores itemsInStock count

Translate to Spanish

I believe it would be nice to translate the README.md to Spanish and would love to help!

Fucking Awesome !

Nice, it is so useful for us !

A* algorithm?

Hey! This repo is awesome! Nice job!

While I was reading through the algorithms, I found weird that the A* algorithm was missing, which is one of the few I know.

I'm just gonna leave this as a suggestion, sorry if I can't do a pull request!

Trie - remove words

Removing words in a Trie seems equally important as adding words. It would be nice to have that.

I'm not sure what this is called or if it belongs here

Hey, I apologize in advance if this is misplaced. I don't have any maths education or know anything of algorithms.

I've been working on something that I believe I misconstrued from a problem I saw asked that dealt with binary trees. I don't know if this is a valid algorithm or not:

// Find all subtrees of n-ary tree. For example:
//
//          1
//        /   \
//       /     \
//      2       3
//     / \     /|\
//    4   6   5 7 8
//       / \
//      9  10
       
// I want to show all subtrees:

// 1    1   1       1       1        1         1
//     /     \     / \     / \      / \         \
//    2       3   2   3   2   3    2   3         3
//                        |        |  /         /
//                        4        4 5         5

I think essentially what I'm trying to communicate here is any valid branching path/"state" from the tree starting at the root node. I first tried order-specific (all permutations of each "level" were valid) but this was far too difficult and I've since retreated to trying to figure out order-inspecific. I could be way off, but this appears to work:

https://repl.it/@GavinRay97/VivaciousWarmheartedComputers-1

Console Output of Trees - CLICK TO EXPAND

var exampleTree = {
  a: {
    b: {
      d: null,
      e: {
        f: null,
        g: {
          i: {
            l: null,
            m: null,
            n: null,
          },
          k: null,
        },
        h: null
      }
    },
    c: null,
    o: null
  },
}

"a -> b"
"a -> b-c"
"a -> b-c -> d"
"a -> b-c -> d-e"
"a -> b-c -> d-e -> f"
"a -> b-c -> d-e -> f-g"
"a -> b-c -> d-e -> f-g-h"
"a -> b-c -> d-e -> f-g-h -> i"
"a -> b-c -> d-e -> f-g-h -> i-k"
"a -> b-c -> d-e -> f-g-h -> i-k -> l"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> m"
"a -> b-c -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> n"
"a -> b-c -> d-e -> f-g-h -> i -> l"
"a -> b-c -> d-e -> f-g-h -> i -> l-m"
"a -> b-c -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i -> m"
"a -> b-c -> d-e -> f-g-h -> i -> m-n"
"a -> b-c -> d-e -> f-g-h -> i -> n"
"a -> b-c -> d-e -> f-g-h -> k"
"a -> b-c -> d-e -> f-g -> i"
"a -> b-c -> d-e -> f-g -> i-k"
"a -> b-c -> d-e -> f-g -> i-k -> l"
"a -> b-c -> d-e -> f-g -> i-k -> l-m"
"a -> b-c -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g -> i-k -> m"
"a -> b-c -> d-e -> f-g -> i-k -> m-n"
"a -> b-c -> d-e -> f-g -> i-k -> n"
"a -> b-c -> d-e -> f-g -> i -> l"
"a -> b-c -> d-e -> f-g -> i -> l-m"
"a -> b-c -> d-e -> f-g -> i -> l-m-n"
"a -> b-c -> d-e -> f-g -> i -> m"
"a -> b-c -> d-e -> f-g -> i -> m-n"
"a -> b-c -> d-e -> f-g -> i -> n"
"a -> b-c -> d-e -> f-g -> k"
"a -> b-c -> d-e -> g"
"a -> b-c -> d-e -> g-h"
"a -> b-c -> d-e -> g-h -> i"
"a -> b-c -> d-e -> g-h -> i-k"
"a -> b-c -> d-e -> g-h -> i-k -> l"
"a -> b-c -> d-e -> g-h -> i-k -> l-m"
"a -> b-c -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> g-h -> i-k -> m"
"a -> b-c -> d-e -> g-h -> i-k -> m-n"
"a -> b-c -> d-e -> g-h -> i-k -> n"
"a -> b-c -> d-e -> g-h -> i -> l"
"a -> b-c -> d-e -> g-h -> i -> l-m"
"a -> b-c -> d-e -> g-h -> i -> l-m-n"
"a -> b-c -> d-e -> g-h -> i -> m"
"a -> b-c -> d-e -> g-h -> i -> m-n"
"a -> b-c -> d-e -> g-h -> i -> n"
"a -> b-c -> d-e -> g-h -> k"
"a -> b-c -> d-e -> g -> i"
"a -> b-c -> d-e -> g -> i-k"
"a -> b-c -> d-e -> g -> i-k -> l"
"a -> b-c -> d-e -> g -> i-k -> l-m"
"a -> b-c -> d-e -> g -> i-k -> l-m-n"
"a -> b-c -> d-e -> g -> i-k -> m"
"a -> b-c -> d-e -> g -> i-k -> m-n"
"a -> b-c -> d-e -> g -> i-k -> n"
"a -> b-c -> d-e -> g -> i -> l"
"a -> b-c -> d-e -> g -> i -> l-m"
"a -> b-c -> d-e -> g -> i -> l-m-n"
"a -> b-c -> d-e -> g -> i -> m"
"a -> b-c -> d-e -> g -> i -> m-n"
"a -> b-c -> d-e -> g -> i -> n"
"a -> b-c -> d-e -> g -> k"
"a -> b-c -> d-e -> h"
"a -> b-c -> e"
"a -> b-c -> e -> f"
"a -> b-c -> e -> f-g"
"a -> b-c -> e -> f-g-h"
"a -> b-c -> e -> f-g-h -> i"
"a -> b-c -> e -> f-g-h -> i-k"
"a -> b-c -> e -> f-g-h -> i-k -> l"
"a -> b-c -> e -> f-g-h -> i-k -> l-m"
"a -> b-c -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> e -> f-g-h -> i-k -> m"
"a -> b-c -> e -> f-g-h -> i-k -> m-n"
"a -> b-c -> e -> f-g-h -> i-k -> n"
"a -> b-c -> e -> f-g-h -> i -> l"
"a -> b-c -> e -> f-g-h -> i -> l-m"
"a -> b-c -> e -> f-g-h -> i -> l-m-n"
"a -> b-c -> e -> f-g-h -> i -> m"
"a -> b-c -> e -> f-g-h -> i -> m-n"
"a -> b-c -> e -> f-g-h -> i -> n"
"a -> b-c -> e -> f-g-h -> k"
"a -> b-c -> e -> f-g -> i"
"a -> b-c -> e -> f-g -> i-k"
"a -> b-c -> e -> f-g -> i-k -> l"
"a -> b-c -> e -> f-g -> i-k -> l-m"
"a -> b-c -> e -> f-g -> i-k -> l-m-n"
"a -> b-c -> e -> f-g -> i-k -> m"
"a -> b-c -> e -> f-g -> i-k -> m-n"
"a -> b-c -> e -> f-g -> i-k -> n"
"a -> b-c -> e -> f-g -> i -> l"
"a -> b-c -> e -> f-g -> i -> l-m"
"a -> b-c -> e -> f-g -> i -> l-m-n"
"a -> b-c -> e -> f-g -> i -> m"
"a -> b-c -> e -> f-g -> i -> m-n"
"a -> b-c -> e -> f-g -> i -> n"
"a -> b-c -> e -> f-g -> k"
"a -> b-c -> e -> g"
"a -> b-c -> e -> g-h"
"a -> b-c -> e -> g-h -> i"
"a -> b-c -> e -> g-h -> i-k"
"a -> b-c -> e -> g-h -> i-k -> l"
"a -> b-c -> e -> g-h -> i-k -> l-m"
"a -> b-c -> e -> g-h -> i-k -> l-m-n"
"a -> b-c -> e -> g-h -> i-k -> m"
"a -> b-c -> e -> g-h -> i-k -> m-n"
"a -> b-c -> e -> g-h -> i-k -> n"
"a -> b-c -> e -> g-h -> i -> l"
"a -> b-c -> e -> g-h -> i -> l-m"
"a -> b-c -> e -> g-h -> i -> l-m-n"
"a -> b-c -> e -> g-h -> i -> m"
"a -> b-c -> e -> g-h -> i -> m-n"
"a -> b-c -> e -> g-h -> i -> n"
"a -> b-c -> e -> g-h -> k"
"a -> b-c -> e -> g -> i"
"a -> b-c -> e -> g -> i-k"
"a -> b-c -> e -> g -> i-k -> l"
"a -> b-c -> e -> g -> i-k -> l-m"
"a -> b-c -> e -> g -> i-k -> l-m-n"
"a -> b-c -> e -> g -> i-k -> m"
"a -> b-c -> e -> g -> i-k -> m-n"
"a -> b-c -> e -> g -> i-k -> n"
"a -> b-c -> e -> g -> i -> l"
"a -> b-c -> e -> g -> i -> l-m"
"a -> b-c -> e -> g -> i -> l-m-n"
"a -> b-c -> e -> g -> i -> m"
"a -> b-c -> e -> g -> i -> m-n"
"a -> b-c -> e -> g -> i -> n"
"a -> b-c -> e -> g -> k"
"a -> b-c -> e -> h"
"a -> b-c-o"
"a -> b-c-o -> d"
"a -> b-c-o -> d-e"
"a -> b-c-o -> d-e -> f"
"a -> b-c-o -> d-e -> f-g"
"a -> b-c-o -> d-e -> f-g-h"
"a -> b-c-o -> d-e -> f-g-h -> i"
"a -> b-c-o -> d-e -> f-g-h -> i-k"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> n"
"a -> b-c-o -> d-e -> f-g-h -> i -> l"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> m"
"a -> b-c-o -> d-e -> f-g-h -> i -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> n"
"a -> b-c-o -> d-e -> f-g-h -> k"
"a -> b-c-o -> d-e -> f-g -> i"
"a -> b-c-o -> d-e -> f-g -> i-k"
"a -> b-c-o -> d-e -> f-g -> i-k -> l"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> m"
"a -> b-c-o -> d-e -> f-g -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> n"
"a -> b-c-o -> d-e -> f-g -> i -> l"
"a -> b-c-o -> d-e -> f-g -> i -> l-m"
"a -> b-c-o -> d-e -> f-g -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i -> m"
"a -> b-c-o -> d-e -> f-g -> i -> m-n"
"a -> b-c-o -> d-e -> f-g -> i -> n"
"a -> b-c-o -> d-e -> f-g -> k"
"a -> b-c-o -> d-e -> g"
"a -> b-c-o -> d-e -> g-h"
"a -> b-c-o -> d-e -> g-h -> i"
"a -> b-c-o -> d-e -> g-h -> i-k"
"a -> b-c-o -> d-e -> g-h -> i-k -> l"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> m"
"a -> b-c-o -> d-e -> g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> n"
"a -> b-c-o -> d-e -> g-h -> i -> l"
"a -> b-c-o -> d-e -> g-h -> i -> l-m"
"a -> b-c-o -> d-e -> g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i -> m"
"a -> b-c-o -> d-e -> g-h -> i -> m-n"
"a -> b-c-o -> d-e -> g-h -> i -> n"
"a -> b-c-o -> d-e -> g-h -> k"
"a -> b-c-o -> d-e -> g -> i"
"a -> b-c-o -> d-e -> g -> i-k"
"a -> b-c-o -> d-e -> g -> i-k -> l"
"a -> b-c-o -> d-e -> g -> i-k -> l-m"
"a -> b-c-o -> d-e -> g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g -> i-k -> m"
"a -> b-c-o -> d-e -> g -> i-k -> m-n"
"a -> b-c-o -> d-e -> g -> i-k -> n"
"a -> b-c-o -> d-e -> g -> i -> l"
"a -> b-c-o -> d-e -> g -> i -> l-m"
"a -> b-c-o -> d-e -> g -> i -> l-m-n"
"a -> b-c-o -> d-e -> g -> i -> m"
"a -> b-c-o -> d-e -> g -> i -> m-n"
"a -> b-c-o -> d-e -> g -> i -> n"
"a -> b-c-o -> d-e -> g -> k"
"a -> b-c-o -> d-e -> h"
"a -> b-c-o -> e"
"a -> b-c-o -> e -> f"
"a -> b-c-o -> e -> f-g"
"a -> b-c-o -> e -> f-g-h"
"a -> b-c-o -> e -> f-g-h -> i"
"a -> b-c-o -> e -> f-g-h -> i-k"
"a -> b-c-o -> e -> f-g-h -> i-k -> l"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> m"
"a -> b-c-o -> e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> n"
"a -> b-c-o -> e -> f-g-h -> i -> l"
"a -> b-c-o -> e -> f-g-h -> i -> l-m"
"a -> b-c-o -> e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i -> m"
"a -> b-c-o -> e -> f-g-h -> i -> m-n"
"a -> b-c-o -> e -> f-g-h -> i -> n"
"a -> b-c-o -> e -> f-g-h -> k"
"a -> b-c-o -> e -> f-g -> i"
"a -> b-c-o -> e -> f-g -> i-k"
"a -> b-c-o -> e -> f-g -> i-k -> l"
"a -> b-c-o -> e -> f-g -> i-k -> l-m"
"a -> b-c-o -> e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g -> i-k -> m"
"a -> b-c-o -> e -> f-g -> i-k -> m-n"
"a -> b-c-o -> e -> f-g -> i-k -> n"
"a -> b-c-o -> e -> f-g -> i -> l"
"a -> b-c-o -> e -> f-g -> i -> l-m"
"a -> b-c-o -> e -> f-g -> i -> l-m-n"
"a -> b-c-o -> e -> f-g -> i -> m"
"a -> b-c-o -> e -> f-g -> i -> m-n"
"a -> b-c-o -> e -> f-g -> i -> n"
"a -> b-c-o -> e -> f-g -> k"
"a -> b-c-o -> e -> g"
"a -> b-c-o -> e -> g-h"
"a -> b-c-o -> e -> g-h -> i"
"a -> b-c-o -> e -> g-h -> i-k"
"a -> b-c-o -> e -> g-h -> i-k -> l"
"a -> b-c-o -> e -> g-h -> i-k -> l-m"
"a -> b-c-o -> e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> g-h -> i-k -> m"
"a -> b-c-o -> e -> g-h -> i-k -> m-n"
"a -> b-c-o -> e -> g-h -> i-k -> n"
"a -> b-c-o -> e -> g-h -> i -> l"
"a -> b-c-o -> e -> g-h -> i -> l-m"
"a -> b-c-o -> e -> g-h -> i -> l-m-n"
"a -> b-c-o -> e -> g-h -> i -> m"
"a -> b-c-o -> e -> g-h -> i -> m-n"
"a -> b-c-o -> e -> g-h -> i -> n"
"a -> b-c-o -> e -> g-h -> k"
"a -> b-c-o -> e -> g -> i"
"a -> b-c-o -> e -> g -> i-k"
"a -> b-c-o -> e -> g -> i-k -> l"
"a -> b-c-o -> e -> g -> i-k -> l-m"
"a -> b-c-o -> e -> g -> i-k -> l-m-n"
"a -> b-c-o -> e -> g -> i-k -> m"
"a -> b-c-o -> e -> g -> i-k -> m-n"
"a -> b-c-o -> e -> g -> i-k -> n"
"a -> b-c-o -> e -> g -> i -> l"
"a -> b-c-o -> e -> g -> i -> l-m"
"a -> b-c-o -> e -> g -> i -> l-m-n"
"a -> b-c-o -> e -> g -> i -> m"
"a -> b-c-o -> e -> g -> i -> m-n"
"a -> b-c-o -> e -> g -> i -> n"
"a -> b-c-o -> e -> g -> k"
"a -> b-c-o -> e -> h"
"a -> b -> d"
"a -> b -> d-e"
"a -> b -> d-e -> f"
"a -> b -> d-e -> f-g"
"a -> b -> d-e -> f-g-h"
"a -> b -> d-e -> f-g-h -> i"
"a -> b -> d-e -> f-g-h -> i-k"
"a -> b -> d-e -> f-g-h -> i-k -> l"
"a -> b -> d-e -> f-g-h -> i-k -> l-m"
"a -> b -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b -> d-e -> f-g-h -> i-k -> m"
"a -> b -> d-e -> f-g-h -> i-k -> m-n"
"a -> b -> d-e -> f-g-h -> i-k -> n"
"a -> b -> d-e -> f-g-h -> i -> l"
"a -> b -> d-e -> f-g-h -> i -> l-m"
"a -> b -> d-e -> f-g-h -> i -> l-m-n"
"a -> b -> d-e -> f-g-h -> i -> m"
"a -> b -> d-e -> f-g-h -> i -> m-n"
"a -> b -> d-e -> f-g-h -> i -> n"
"a -> b -> d-e -> f-g-h -> k"
"a -> b -> d-e -> f-g -> i"
"a -> b -> d-e -> f-g -> i-k"
"a -> b -> d-e -> f-g -> i-k -> l"
"a -> b -> d-e -> f-g -> i-k -> l-m"
"a -> b -> d-e -> f-g -> i-k -> l-m-n"
"a -> b -> d-e -> f-g -> i-k -> m"
"a -> b -> d-e -> f-g -> i-k -> m-n"
"a -> b -> d-e -> f-g -> i-k -> n"
"a -> b -> d-e -> f-g -> i -> l"
"a -> b -> d-e -> f-g -> i -> l-m"
"a -> b -> d-e -> f-g -> i -> l-m-n"
"a -> b -> d-e -> f-g -> i -> m"
"a -> b -> d-e -> f-g -> i -> m-n"
"a -> b -> d-e -> f-g -> i -> n"
"a -> b -> d-e -> f-g -> k"
"a -> b -> d-e -> g"
"a -> b -> d-e -> g-h"
"a -> b -> d-e -> g-h -> i"
"a -> b -> d-e -> g-h -> i-k"
"a -> b -> d-e -> g-h -> i-k -> l"
"a -> b -> d-e -> g-h -> i-k -> l-m"
"a -> b -> d-e -> g-h -> i-k -> l-m-n"
"a -> b -> d-e -> g-h -> i-k -> m"
"a -> b -> d-e -> g-h -> i-k -> m-n"
"a -> b -> d-e -> g-h -> i-k -> n"
"a -> b -> d-e -> g-h -> i -> l"
"a -> b -> d-e -> g-h -> i -> l-m"
"a -> b -> d-e -> g-h -> i -> l-m-n"
"a -> b -> d-e -> g-h -> i -> m"
"a -> b -> d-e -> g-h -> i -> m-n"
"a -> b -> d-e -> g-h -> i -> n"
"a -> b -> d-e -> g-h -> k"
"a -> b -> d-e -> g -> i"
"a -> b -> d-e -> g -> i-k"
"a -> b -> d-e -> g -> i-k -> l"
"a -> b -> d-e -> g -> i-k -> l-m"
"a -> b -> d-e -> g -> i-k -> l-m-n"
"a -> b -> d-e -> g -> i-k -> m"
"a -> b -> d-e -> g -> i-k -> m-n"
"a -> b -> d-e -> g -> i-k -> n"
"a -> b -> d-e -> g -> i -> l"
"a -> b -> d-e -> g -> i -> l-m"
"a -> b -> d-e -> g -> i -> l-m-n"
"a -> b -> d-e -> g -> i -> m"
"a -> b -> d-e -> g -> i -> m-n"
"a -> b -> d-e -> g -> i -> n"
"a -> b -> d-e -> g -> k"
"a -> b -> d-e -> h"
"a -> b -> e"
"a -> b -> e -> f"
"a -> b -> e -> f-g"
"a -> b -> e -> f-g-h"
"a -> b -> e -> f-g-h -> i"
"a -> b -> e -> f-g-h -> i-k"
"a -> b -> e -> f-g-h -> i-k -> l"
"a -> b -> e -> f-g-h -> i-k -> l-m"
"a -> b -> e -> f-g-h -> i-k -> l-m-n"
"a -> b -> e -> f-g-h -> i-k -> m"
"a -> b -> e -> f-g-h -> i-k -> m-n"
"a -> b -> e -> f-g-h -> i-k -> n"
"a -> b -> e -> f-g-h -> i -> l"
"a -> b -> e -> f-g-h -> i -> l-m"
"a -> b -> e -> f-g-h -> i -> l-m-n"
"a -> b -> e -> f-g-h -> i -> m"
"a -> b -> e -> f-g-h -> i -> m-n"
"a -> b -> e -> f-g-h -> i -> n"
"a -> b -> e -> f-g-h -> k"
"a -> b -> e -> f-g -> i"
"a -> b -> e -> f-g -> i-k"
"a -> b -> e -> f-g -> i-k -> l"
"a -> b -> e -> f-g -> i-k -> l-m"
"a -> b -> e -> f-g -> i-k -> l-m-n"
"a -> b -> e -> f-g -> i-k -> m"
"a -> b -> e -> f-g -> i-k -> m-n"
"a -> b -> e -> f-g -> i-k -> n"
"a -> b -> e -> f-g -> i -> l"
"a -> b -> e -> f-g -> i -> l-m"
"a -> b -> e -> f-g -> i -> l-m-n"
"a -> b -> e -> f-g -> i -> m"
"a -> b -> e -> f-g -> i -> m-n"
"a -> b -> e -> f-g -> i -> n"
"a -> b -> e -> f-g -> k"
"a -> b -> e -> g"
"a -> b -> e -> g-h"
"a -> b -> e -> g-h -> i"
"a -> b -> e -> g-h -> i-k"
"a -> b -> e -> g-h -> i-k -> l"
"a -> b -> e -> g-h -> i-k -> l-m"
"a -> b -> e -> g-h -> i-k -> l-m-n"
"a -> b -> e -> g-h -> i-k -> m"
"a -> b -> e -> g-h -> i-k -> m-n"
"a -> b -> e -> g-h -> i-k -> n"
"a -> b -> e -> g-h -> i -> l"
"a -> b -> e -> g-h -> i -> l-m"
"a -> b -> e -> g-h -> i -> l-m-n"
"a -> b -> e -> g-h -> i -> m"
"a -> b -> e -> g-h -> i -> m-n"
"a -> b -> e -> g-h -> i -> n"
"a -> b -> e -> g-h -> k"
"a -> b -> e -> g -> i"
"a -> b -> e -> g -> i-k"
"a -> b -> e -> g -> i-k -> l"
"a -> b -> e -> g -> i-k -> l-m"
"a -> b -> e -> g -> i-k -> l-m-n"
"a -> b -> e -> g -> i-k -> m"
"a -> b -> e -> g -> i-k -> m-n"
"a -> b -> e -> g -> i-k -> n"
"a -> b -> e -> g -> i -> l"
"a -> b -> e -> g -> i -> l-m"
"a -> b -> e -> g -> i -> l-m-n"
"a -> b -> e -> g -> i -> m"
"a -> b -> e -> g -> i -> m-n"
"a -> b -> e -> g -> i -> n"
"a -> b -> e -> g -> k"
"a -> b -> e -> h"
"a -> c"
"a -> c-o"
"a -> o"
Results (plus head node):  412

Could anyone tell me whether the problem I'm describing is a real/existing algorithm, and how bad/far off my solution is so far? It's probably O(n^10) or something ridiculous too.

Thank you!

Translate to korean

Hello!!
I want to translate README into Korean.
Can I?
And, are there any restriction?

Needs Pseudocode?

I'm thinking of adding pseudocode to the readme based on DSA by Granville Barnett and Luca Del Tongo. Would this be useful?

Longest common substring does not handle unicode properly

It seems that the algorithm longestCommonSubstring does not handle unicode characters properly:

longestCommonSubstr('𐌵𐌵**ABC', '𐌵𐌵--ABC') === '𐌵𐌵'
// whereas the longest one should be ABC (in terms of number of code points)

// Number of code points:
[...'𐌵𐌵'].length === 2
[...'ABC'].length === 3

// Number of "characters":
'𐌵𐌵'.length === 4
'ABC'.length === 3

You should maybe add a note on the algorithm regarding this. Basically the problem can occur whenever the strings contain characters outside the BMP range (ie code points greater than 0xffff).

Feel free to close the issue whenever you want. The aim was just to signal the problem is case you want to patch it in a way.

primality test failure

the primality test won't work for float between 1 and 3

Wrong description

Please add correct description for javascript-algorithms/src/data-structures/linked-list/LinkedList.js, because comment in Delete function is misleading:
// If the head must be deleted then make 2nd node to be a head.

It would be better to add:
'while' will delete all nodes with the same value, starting with the this.head.

Workshopper

How about creating a workshopper? I would love to create one.

My concern about no classification by Procedural/Imperative and Functional programming Paradigm

Hi, this is a great project. Thanks.
I have a concern that I would like to share.

For instance, looking at /algorithms/math/factorial which is one of the most basic math topic:
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/factorial

I found 2 implementations:

factorial.js

export default function factorial(number) {
  let result = 1;

  for (let i = 2; i <= number; i += 1) {
    result *= i;
  }

  return result;
}

factorialRecursive.js

export default function factorialRecursive(number) {
  return number > 1 ? number * factorialRecursive(number - 1) : 1;
}

factorial.js is a code of Procedural/Imperative programming style, and uses mutable variables.

factorialRecursive.js is recursive, and can be said functional programming style, immutable. Alghouth this is a typical implementation which I can see everywhere, in terms of "Big O notations". this is rather anti-pattern.

A better or I would say, a proper way is,

factorialFunctional.js

//[...Array(5).keys()]
//-> [ 0, 1, 2, 3 ,4 ]

const natural = n => {
    const arr0 = [...Array(n + 1).keys()];
    const [first, ...arr] = arr0;
    return arr;
};

console.log(
    natural(5) //[ 1, 2, 3, 4, 5 ]
);

function factorialFunctional(number) {
    const list = number < 1
        ? [1]
        : natural(number)
    const multiply = (a, b) => a * b;
    return list.reduce(multiply);
}

console.log(
    factorialFunctional(5)//120
);

This is as efficient as the factorial.js in terms of "Big O notations", and immutable.

I think when algorithms are presented, it's significantly important to clarify what kind of programming paradigm the algorithms are based on.

Currently, it seems the contributions are updated randomly without formal classification for them, and I think it's a good idea to show a guideline in the README that to clarify which paradigm every algorithm belongs to. In this manner, a contributors notice "oh, here, there is no Functional or Imperative pattern yet, so I will add.."

Thanks.

Add Red Black Tree

Hello,

I have once write Red Black Tree in Java and interesting to write another version in Javascript. Anyone have already working on it? If no one, maybe I will pull the Red Black Tree tonight.

Regard,
Hafidz

Add B-Tree

I would like to contriblute to adding the B-Tree data structure.
It is a rather common data structure that is great for large data, I'll be glad to implement it.

Add Max Heap?

A Max Heap DS would be terrific in this repo. Should I work on it and submit a PR? I'm also open to other DS or algorithm contributions.

Translate to Polish

Hi, can I translate the README.md to Polish? Thanks.

removeChild in BinaryTreeNode does not remove parent from child

Apologies if this is the expected behavior. In BinaryTreeNode.js, the function removeChild sets either this.left or this.right to null, but does not set nodeToRemove.parent to null. So for example the following test fails:

const rootNode = new BinarySearchTreeNode('foo');
rootNode.insert('bar');
const childNode = rootNode.find('bar');
rootNode.remove('bar');
expect(childNode.parent).toBeNull();

Duplicate Code in peek in Stack.js

I'd of thought you'd do it like -

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.linkedList.tail.value;
}

A suggestion about Factorial

Not an issue - more of a suggestion. Is it better to start the loop from 2？

export default function factorial(number) {
  let result = 1;

  for (let i = 2; i <= number; i += 1) {
    result *= i;
  }

  return result;
}

Rename `QuickSortInPlace` to `TrueQuickSort` or something similar.

It should be mentioned that QuickSortInPlace is the actual quick sort. Other implementation that allows using extra space is like quick sort but not the strictly the actual algorithm.

I've seen this at several places. For example the following implementation of quicksort in Haskell

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted  

It is shown as a quicksort implementation but in reality it is not.
A lot of newbies will get a wrong idea about the quicksort this way who are only learning algos this way.
It should at least be mentioned in the ReadMe that the one with the in-place is the real one.

Sharing similar effort: algorithms-js

Hi @trekhleb,

This is one amazing project. Thank you for working on it.

I just wanted to quickly share a similar effort I made last year for building a consumable algorithms and data structure library. I did heavily test it. I hope this might help someone.

https://github.com/ManrajGrover/algorithms-js

Maybe, we can link it in README somewhere?

Add Liu Hui's π algorithm

https://en.wikipedia.org/wiki/Liu_Hui's_%CF%80_algorithm

e.g:

const getSideLength = (sideLength, count) => {
  if (count <= 0) return sideLength;
  const m = sideLength / 2;
  const g = Math.sqrt((0.5 ** 2) - (m ** 2));
  const j = 0.5 - g;
  return getSideLength(Math.sqrt((j ** 2) + (m ** 2)), count - 1);
};


const pi = (splitCount = 0) => {
  const sideLength = getSideLength(0.5, splitCount);
  const sideCount = 6 * (splitCount ? 2 ** splitCount : 1);
  return sideLength * sideCount;
};

// for (let i = 0; i < 100; i += 1) {
//   const p = pi(i);
//   console.log(i, p, p === Math.PI);
// }

export default pi;

bug in AVL tree rotateLeftRight and rotateRightLeft

in rotateLeftRight, while leftRightNode has left child, it will be lost.
also as well rotateRightLeft.

the following code is my correction.

 rotateLeftRight(rootNode) {
    // Detach left node from rootNode since it is going to be replaced.
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // Detach right node from leftNode.
    const leftRightNode = leftNode.right;
    leftNode.setRight(null);

    if (leftRightNode.left) {
      leftNode.setRight(leftRightNode.left);
      leftRightNode.setLeft(null);
    }

    // Attach leftRightNode to the rootNode.
    rootNode.setLeft(leftRightNode);

    // Attach leftNode as left node for leftRight node.
    leftRightNode.setLeft(leftNode);

    // Do left-left rotation.
    this.rotateLeftLeft(rootNode);
  }

  rotateRightLeft(rootNode) {
    // Detach right node from rootNode since it is going to be replaced.
    const rightNode = rootNode.right;
    rootNode.setRight(null);

    // Detach left node from rightNode.
    const rightLeftNode = rightNode.left;
    rightNode.setLeft(null);

    if (rightLeftNode.right) {
      rightNode.setLeft(rightLeftNode.right);
      rightLeftNode.setRight(null);
    }

    // Attach rightLeftNode to the rootNode.
    rootNode.setRight(rightLeftNode);

    // Attach rightNode as right node for rightLeft node.
    rightLeftNode.setRight(rightNode);

    // Do right-right rotation.
    this.rotateRightRight(rootNode);
  }

What should be returned by the remove method of the BinarySearchTreeNode?

Hi! The remove method returns a BinarySearchTreeNode object. But there is one uncertain moment. What should be contained in the properties of this object, such as the parent, left, right? Are these properties relevant? Or they must be null?

Add another section

You've created a wonderful repository!
It's really interesting, especially for learning purposes, like in my case.

What do you think about adding a new section that explains how to calculate 3D geometry functions?

removal from linkedlist

"This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration." - Not correct for removal. Deleting a node from a linked list is not efficient as you have to traverse the list (in case it is very large list then it will not be optimal) The option is to use Vector.

run repo's class? nodejs not support ES6 import

i want to wirte a js to test a data-structures class ,as queue, but this js file can't run on lastest version nodejs? how can i run my test?

What about rope?

I found this repo while looking for a good example of rope. But I can't find one :(

Implementing Binary Indexed Tree

Hi! I'm new to this repository and would like to try to implement the binary indexed tree!

the picture about Red-Black Tree is not match

see javascript-algorithms/src/data-structures/tree/red-black-tree/readme.md
There are four pictures describe the red-black tree's four cases(LL /LR /RR /RL).But the Right Right Case and the Right Left Case 's picture are the same.

Fibonacci sequences

Not an issue - more of a suggestion. Would be good to return an array for the fibonacci sequence, as well as the sequence at nth position (and maybe rename the nth-position fibonacciNth() or something). For example:

export default function fibonacci(steps) {
  const fibSequence = [];

  let currentValue = 1;
  let previousValue = 0;

  if(steps === 1) {
    return [1];
  }

  while(steps--) {
    currentValue += previousValue;
    previousValue = (currentValue - previousValue);

    fibSequence.push(currentValue);
  }

  return fibSequence;
}

And:

export default function fibonacciNth(steps) {
  let currentValue = 1;
  let previousValue = 0;

  if(steps === 1) {
    return 1;
  }

  while(steps--) {
    currentValue += previousValue;
    previousValue = (currentValue - previousValue);
  }

  return currentValue;
}

Also, where before there was a:

while(iterationsCounter) {
  // Do code
  
  iterationsCounter -= 1;
}

This is mildly verbose, and can be more succinctly written without detriment to legibility as:

while(iterationsCounter--) {
  // Do code
}

Personally I think that's more readable. Happy to do a PR?

Edit: camel cased variable names to match existing code

TSP or TPP Algorithm

I'm looking for any implementation of Multiple Travelers Purchase Problem, any idea ?

Combination without repetition algorithm difficult to understand

##I found the algorithm is so hard to understand that I almost pulled my hairs off. I tried to analyze it in Python tutor but It didn't get easier. After struggling for a few hours, I figured a solution that is more expressive and easier to understand.

function comboWithoutRepeat(chooseFrom, numChosen) {
  const combinations = []
  function recursive(chooseFrom, numChosen, path = []) {
    if (numChosen === 0) {
      combinations.push(path)
      return
    }
    for (let i = 0; i <= chooseFrom.length - numChosen; i++) {
      const letter = chooseFrom[i]
      const rest = chooseFrom.slice(i + 1)
      recursive(rest, numChosen - 1, [letter].concat(path))
    }
  }
  recursive(chooseFrom, numChosen)
  return combinations
}

console.log(comboWithoutRepeat([1, 2, 3, 4], 3, ''))

Test suite failed to run on Ubuntu

Test suite failed to run

SecurityError: localStorage is not available for opaque origins

  at Window.get localStorage [as localStorage] (node_modules/jsdom/lib/jsdom/browser/Window.js:257:15)
      at Array.forEach (<anonymous>)

Floyd–Warshall algorithm

https://www.wikiwand.com/en/Floyd%E2%80%93Warshall_algorithm

Z -algorithm

I'm new to open source,I wanted to implement z-algorithm for strings