# Posts tagged as “Algorithm Template”

## DFS Template

Use on Binary Tree, Permutation or Combination problems

• Time complexity：
• Tree traversal: O(n)
• Permutation: O(n! * n)
• Combination: O(2n * n)
``````function dfs(nums, n, start, cur, res...) {
if (exit recursive condition) {
return;
}
for (possible solution) {
// modify current state
dfs(nums, n, i + 1, cur, res...);
// recover current state

}
return something if need // option
};``````

## BFS Template

Use on Topological Sorting, Level Traversal, Shortest path in graph, Union Find problems

• Time complexity：O(n + m) // n is node, m is edge
• Space complexity: O(n)
``````// 1. No level:
function bfs(node) {
const queue = [];
queue.push(node);

while(queue.length !== 0) {
...
let cur = queue.shift();
for (neighbor in cur\'s neighbors) {
if (neighbor is valid but not visit)
queue.push(neighbor)
}
}
}

// 2. Has level traversal: depends on the questions
// Level could be a number or array
function bfs(node) {
const queue = [];
queue.push(node);
// (1) let level = 0; // level as a number for tracking
while(queue.length !== 0) {
let size = queue.length;
// (2) let level = []; // level could be storing data
while(size--) {
let cur = queue.shift();
for (neighbor in cur\'s neighbors) {
if (neighbor is valid but not visit)
queue.push(neighbor)
}
}
//(1) level++;
//(2) res.push(level.concat()); // adding to the result
}
}

// 3. BFS - finding the shortest path in graph
function bfs(node) {
const queue = [];
let distance = new Map(); // avoid duplicate, track startNode
queue.push(startNode);
distance.set(startNode, 0); // or 1 depends on the question

while(queue.length !== 0) {
let cur = queue.shift();
if (node is destination) {
break or return something;
}
for (neighbor in cur\'s neighbors) {
if (distance.has(neighbor)) continue;
queue.push(neighbor);
distance.set(neighbor, distance.get(node) + 1);
}
}
// possible return:
return distance;
return distance.keys();
return distnace.get(endNode);
...
}``````

## Topological Sorting (BFS) Template:

``````function topologicalSort(nodes) {
const queue = [];
let indegrees = getIndegrees(nodes); // 统计所有点的入度信息 as hashmap
// add those indegree === 0 nodes into queue
for (node of nodes) {
if (indegrees.get(node) === 0)
queue.push(node);
}

let topoOrder = [];
while(queue.length !== 0) {
let cur = queue.shift();
topoOrder.push(cur);
for (neighbor in cur\'s neighbors) {
indegrees.set(neighbor, indegrees.get(neighbor) - 1);
// when indegree is 0, no more depends on any node, add to queue
if (indegrees.get(neighbor) === 0) {
queue.push(neighbor);
}
}
if (topoOrder.length !== nodes.length)
return "No topoOrder!";

}``````

## Binary Search Template

• Time complexity O(logn)
• Space complexity O(1)
``````function binarySearch(nums, target) {
let l = 0;
let r = nums.length;

while (l < r) {
let mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) {
// most case: just return target
return mid;
// --- if searching leftBound
// leftBound = mid;
// r = mid;
// --- if searching rightBound
// rightBound = mid;
// l = mid + 1;
} else if (nums[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
}``````

## Merge Sort Template

``````var sortArray = function(nums) {
if (nums === null || nums.length === 0) return;
let temp = [];
mergeSort(nums, 0, nums.length - 1, temp);
return nums;
};

function mergeSort(nums, start, end, temp) {
if (start >= end) return;
// deal with first half
mergeSort(nums, start, Math.floor((start + end) / 2), temp);
// deal with second half
mergeSort(nums, Math.floor((start +end) / 2) + 1, end, temp);
// merge
merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
let mid = Math.floor((start + end) / 2);
let l_index = start;
let r_index = mid + 1;
let index = start;
while (l_index <= mid && r_index <= end) {
if (nums[l_index] < nums[r_index]) {
temp[index++] = nums[l_index++];
} else {
temp[index++] = nums[r_index++];
}
}
while (l_index <= mid)
temp[index++] = nums[l_index++];
while (r_index <= end)
temp[index++] = nums[r_index++];
for (let i = start; i <= end; i++) {
nums[i] = temp[i];
}
}``````

## Quick Sort Template

``````var sortArray = function(nums) {
if (nums === null || nums.length === 0) return;
quickSort(nums, 0, nums.length - 1)
return nums;
};

function quickSort(nums, left, right) {
let index;
if (nums.length > 1) {
// index returned from partition
index = partition(nums, left, right);
// more elements on the left side of the pivot
if (left < index - 1)
quickSort(nums, left, index - 1);
// more elements on the right side of the pivot
if (index < right)
quickSort(nums, index, right);
}
// you can return or not return,
// since we change nums, no need to return
// return nums;
}

function partition(nums, start, end) {
let l = start, r = end;
let mid = Math.floor((start + end) / 2);
let pivot = nums[mid];
// Important: l <= r not l < r
while (l <= r) {
while(nums[l] < pivot)
l++;
while(nums[r] > pivot)
r--;
if (l <= r) {
// swap
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
return l;
}``````

To be continue…