Show Menu

Javascript Algorithmic Cookbook Cheatsheet Cheat Sheet by

These are situations for when to use certain data structure and algorithms

Involving collec­tions

Two Pointer Technique
Two pointers, each starting from the beginning and the end until they both meet OR One pointer moving at a slow pace, while the other pointer moves at twice the speed
Collec­tions are arrays, string, or linked lists. Other applic­ation: searching for pairs in an array, two sorted arrays need to be merged (2 pointers for both arrays), the pattern of using a fast pointer and a slow pointer ( detecting cycles in a linked list)

The Two Heaps Technique

find the earliest or latest meeting at any given time
Finding the median in a large collec­tion.
Largest and smallest values in a set.
To implement a priority queue

Binary Search Technique

Binary search is a technique for finding out whether an item is present in a sorted array or not
It makes use of the fact that if a value is greater than array[i] and the array is sorted, then the value has to lie at index (i+1) or higher. Similarly, if the value is less than array[i], then it has to lie at an index less than i.
Binary search works by comparing the value to search for with the middle item of the array. If the value is higher than the middle item, then the search proceeds in the right half of the array. If the value is less than the middle, then the left sub-array is searched. This process is repeated, and each time, the sub-array within which the value is being searched is reduced by half.
This gives an overall time complexity of O(log n).

Merge Sort Algorithm

Divides the input collection into two portions, recurs­ively calls itself for the two divided portions, and then merges the two sorted portions. Merge Sort Algorithm works in three parts:
Divide: At first, it divides the given collection of elements into two equal halves and then recurs­ively passes these halves to itself. Sorting: Unless, there is only one element left in each half, the division continues, after that, those two end elements (leaf nodes) are sorted. Merging: Finally, the sorted arrays from the top step are merged in order to form the sorted collection of elements
Time Comple­xity: O(NlogN)
Space Comple­xity: O(N)

Bubble Sort Algorithm

The adjacent elements in the collection are compared and the positions are swapped if the first element is greater than the second one. In this way, the largest valued element "­bub­ble­s" to the top.
Usually, after each loop, the elements furthest to the right are in sorted order. The process is continued until all the elements are in sorted order.
Time Comple­xity: O(N2)
Space Comple­xity: O(1)

Keeping track of the "­bal­anc­ing­"

When you want to keep track of what's "­coming in" or incoming and what's what's "­going out" or outgoing

String methods

gets the string length
gets the index of first occurence of the character or a substring in the string.
converts the string to lowercase (or similarly, to upperc­ase).
gets a substring from defined index point in the string.

Array Methods

removes (pops) the last element of an array
method adds new items to the end of an array
method removes the first item of an array
adds new elements to the beginning of an array
sorts the elements of an array in alphab­etical in ascending order
method creates a new array filled with elements that pass a test provided by a function. array.f­il­ter­(fu­nct­ion­(cu­rre­ntV­alue, index, arr), thisValue)
creates a new array from calling a function for every array element.
method calls a function for each element in an array. array.f­or­Eac­h(f­unc­tio­n(c­urr­ent­Value, index, arr), thisValue)
method returns the value of the first element that passes a test. array.f­in­d(f­unc­tio­n(c­urr­ent­Value, index, arr),t­his­Value)
returns true if an array contains a specified value. "­fru­­clu­des­("Ma­ngo­"­);"
reverses the order of the elements in an array
executes a function for each array element. returns true/false if the function returns true/false for all elements.
method returns an array as a string

When to use BFS instead of DFS?

When you need to find the shortest path between any two nodes in an unweighted graph.
If you're solving a problem, and know a solution is not far from the root of the tree, BFS will likely get you there faster.
If the tree is very deep, DFS with heuristics might be faster.

Depth First Search (DFS)

Preorder Traversal
We start from the root node and search the tree vertically (top to bottom), traversing from left to right. The order of visits is ROOT-L­EFT­-RIGHT
In-order Traversal
Start from the leftmost node and move to the right nodes traversing from top to bottom. The order of visits is LEFT-R­OOT­-RIGHT
Post-order Traversal
Start from the leftmost node and move to the right nodes, traversing from bottom to top. The order of visits is LEFT-R­IGH­T-ROOT
In Depth First Search (DFS), a tree is traversed vertically from top to bottom or bottom to top. As you might infer from its namesake, we will traverse as deeply as possible, before moving on to a neighbor node. There are three main ways to apply Depth First Search to a tree.

Time complexity of an array (worst case)


Insertion Sort Algorithm

The collection is virtually split into an ordered and an unordered part. Elements from the unordered portion are picked and placed at the correct index in the ordered part.
Time Comple­xity: O(N2)
Space Comple­xity: O(1)


No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          More Cheat Sheets by briyvonne01

          AngularJS Material Layout Cheatsheet Cheat Sheet