Data Structures and Algorithms Cheat Sheet
by burcuco via cheatography.com/133629/cs/27343/
Arrays & Strings Stack/Queue/Deque
Stores data elements based on an sequential, most commonly 0 Stack Queue Deque Heap
based, index. Last In First First In Last Provides Ascending
Time Complexity Out Out first/last Order
● Indexing: Linear array: O(1), Dynamic array: O(1) push(val) offer(val) offer(val) offer(val)
● Search: Linear array: O(n), Dynamic array: O(n) pop() poll() poll() poll()
● Optimized Search: Linear array: O(log n), Dynamic array: O(log peek() peek() peek() peek()
n)
Implementation in Java:
● Insertion: Linear array: n/a, Dynamic array: O(n)
● Stack<E> stack = new Stack();
Bonus:
● Queue<E> queue = new LinkedList();
● type[] name = {val1, val2, ...}
● Deque<E> deque = new LinkedList();
● Arrays.sort(arr) -> O(n log(n))
● PriorityQueue<E> pq = new PriorityQueue();
● Collections.sort(list) -> O(n log(n))
● int digit = '4' - '0' -> 4
DFS & BFS Big O Notation
● String s = String.valueOf('e') -> "e"
Time Space
● (int) 'a' -> 97 (ASCII)
● new String(char[] arr) ['a','e'] -> "ae" DFS O(E+V) O(Height)
● (char) ('a' + 1) -> 'b' BFS O(E+V) O(Length)
● Character.isLetterOrDigit(char) -> true/false
V & E -> where V is the number of vertices and E is the number of
● new ArrayList<>(anotherList); -> list w/ items
edges.
● StringBuilder.append(char||String)
Height -> where h is the maximum height of the tree.
Length -> where l is the maximum number of nodes in a single level.
Linked List
Stores data with nodes that point to other nodes. DFS vs BFS
Time Complexity DFS BFS
● Indexing: O(n)
●Better when target is closer to ●Better when target is far from
● Search: O(n)
Source. Source.
● Optimized Search: O(n)
●Stack -> LIFO ●Queue -> FIFO
● Append: O(1)
●Preorder, Inorder, Postorder ●Level Order Search
● Prepend: O(1)
Search ●Goes wide
● Insertion: O(n)
●Goes deep ●Iterative
●Recursive ●Slow
HashTable
●Fast
Stores data with key-value pairs.
Time Complexity
● Indexing: O(1)
● Search: O(1)
● Insertion: O(1)
Bonus:
● {1, -1, 0, 2, -2} into map
HashMap {-1, 0, 2, 1, -2} -> any order
LinkedHashMap {1, -1, 0, 2, -2} -> insertion order
TreeMap {-2, -1, 0, 1, 2} -> sorted
● Set doesn't allow duplicates.
● map.getOrDefaultValue(key, default value)
By burcuco Published 30th March, 2021. Sponsored by CrosswordCheats.com
cheatography.com/burcuco/ Last updated 30th March, 2021. Learn to solve cryptic crosswords!
Page 1 of 7. http://crosswordcheats.com
Data Structures and Algorithms Cheat Sheet
by burcuco via cheatography.com/133629/cs/27343/
BFS Impl for Graph BFS Impl. for Level-order Tree Traversal
public boolean connected(int[][] graph, int start, private void printLevelOrder(TreeNode root) {
int end) { Queue<TreeNode> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>(); queue.offer(root);
Queue<Integer> toVisit = new LinkedList<>(); while (!queue.isEmpty()) {
toVisit.enqueue(start); TreeNode tempNode = queue.poll();
while (!toVisit.isEmpty()) { print(tempNode.data + " ");
int curr = toVisit.dequeue();
if (visited.contains(curr)) continue; // add left child
if (curr == end) return true; if (tempNode.left != null) {
for (int i : graph[start]) { queue.offer(tempNode.left);
toVisit.enqueue(i); }
}
visited.add(curr); // add right right child
} if (tempNode.right != null) {
return false; queue.offer(tempNode.right);
} }
}
DFS Impl for Graph }
public boolean connected(int[][] graph, int start,
int end) { DFS Impl. for In-order Tree Traversal
Set<Integer> visited = new HashSet<>(); private void inorder(TreeNode TreeNode) {
return connected(graph, start, end, visited); if (TreeNode == null)
} return;
private boolean connected(int[][] graph, int start, // Traverse left
int end, Set<Integer> visited) { inorder(TreeNode.left);
if (start == end) return true; // Traverse root
if (visited.contains(start)) return false; print(TreeNode.data + " ");
visited.add(start); // Traverse right
for (int i : graph[start]) { inorder(TreeNode.right);
if (connected(graph, i, end, visited)) { }
return true;
}
}
return false;
}
By burcuco Published 30th March, 2021. Sponsored by CrosswordCheats.com
cheatography.com/burcuco/ Last updated 30th March, 2021. Learn to solve cryptic crosswords!
Page 2 of 7. http://crosswordcheats.com
Data Structures and Algorithms Cheat Sheet
by burcuco via cheatography.com/133629/cs/27343/
Dynamic Programming Binary Search Big O Notation
● Dynamic programming is the technique of storing repeated Time Space
computations in memory, rather than recomputing them every time Binary Search O(log n) O(1)
you need them.
● The ultimate goal of this process is to improve runtime. Binary Search - Recursive
● Dynamic programming allows you to use more space to take less
public int binarySearch(int search, int[] array,
time.
int start, int end) {
int middle = start + ((end - start) / 2);
Dynamic Programming Patterns
if(end < start) {
- Minimum (Maximum) Path to Reach a Target
return -1;
Approach: }
Choose minimum (maximum) path among all possible paths before
if (search == array[middle]) {
the current state, then add value for the current state.
return middle;
Formula:
} else if (search < array[middle]) {
routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]
return binarySearch(search, array, start,
- Distinct Ways
middle - 1);
Approach: } else {
Choose minimum (maximum) path among all possible paths before return binarySearch(search, array, middle +
the current state, then add value for the current state. 1, end);
Formula:
}
routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]
}
- Merging Intervals
Approach: Binary Search - Iterative
Find all optimal solutions for every interval and return the best
public int binarySearch(int target, int[] array) {
possible answer
int start = 0;
Formula:
int end = array.length - 1;
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]
while (start <= end) {
- DP on Strings
int middle = start + ((end - start) / 2);
Approach: if (target == array[middle]) {
Compare 2 chars of String or 2 Strings. Do whatever you do. Return. return target;
Formula: } else if (search < array[middle]) {
if s1[i-1] == s2[j-1] then dp[i][j] = //code.
end = middle - 1;
Else dp[i][j] = //code
} else {
- Decision Making start = middle + 1;
Approach: }
If you decide to choose the current value use the previous result }
where the value was ignored; vice-versa, if you decide to ignore the
current value use previous result where value was used.
Formula:
dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});
dp[i][j-1] = max({dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i]});
By burcuco Published 30th March, 2021. Sponsored by CrosswordCheats.com
cheatography.com/burcuco/ Last updated 30th March, 2021. Learn to solve cryptic crosswords!
Page 3 of 7. http://crosswordcheats.com
Data Structures and Algorithms Cheat Sheet
by burcuco via cheatography.com/133629/cs/27343/
Binary Search - Iterative (cont) Merge Sort
return -1; private void mergesort(int low, int high) {
} if (low < high) {
int middle = low + (high - low) / 2;
Bit Manipulation mergesort(low, middle);
Sign Bit 0 -> Positive, 1 -> Negative mergesort(middle + 1, high);
merge(low, middle, high);
AND 0 & 0 -> 0
}
0 & 1 -> 0
1 & 1 -> 1 }
private void merge(int low, int middle, int high)
OR 0 | 0 -> 0
{
0 | 1 -> 1
for (int i = low; i <= high; i++) {
1 | 1 -> 1
helper[i] = numbers[i];
XOR 0 ^ 0 -> 0
}
0 ^ 1 -> 1
int i = low;
1 ^ 1 -> 0
int j = middle + 1;
INVERT ~ 0 -> 1
int k = low;
~ 1 -> 0
while (i <= middle && j <= high) {
Bonus: if (helper[i] <= helper[j]) {
● Shifting
numbers[k] = helper[i];
- Left Shift
i++;
0001 << 0010 (Multiply by 2)
} else {
- Right Shift
numbers[k] = helper[j];
0010 >> 0001 (Division by 2)
j++;
}
● Count 1's of n, Remove last bit
k++;
n = n & (n-1);
● Extract last bit }
n&-n or n&~(n-1) or n^(n&(n-1)) while (i <= middle) {
● n ^ n -> 0 numbers[k] = helper[i];
● n ^ 0 -> n k++;
i++;
Sorting Big O Notation }
Best Average Space }
Merge Sort O(n log(n)) O(n log(n)) O(n)
Heap Sort O(n log(n)) O(n log(n)) O(1)
Quick Sort
Quick Sort O(n log(n)) O(n log(n)) O(log(n))
Insertion Sort O(n) O(n^2) O(1)
Selection Sort O(n^2) O(n^2) O(1)
Bubble Sort O(n) O(n^2) O(1)
private void quicksort(int low, int high) {
int i = low, j = high;
int pivot = numbers[low + (high-low)/2];
while (i <= j) {
while (numbers[i] < pivot) {
i++;
}
while (numbers[j] > pivot) {
j--;
}
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
By burcuco Published 30th March, 2021. Sponsored by CrosswordCheats.com
cheatography.com/burcuco/ Last updated 30th March, 2021. Learn to solve cryptic crosswords!
Page 4 of 7. http://crosswordcheats.com
Data Structures and Algorithms Cheat Sheet
by burcuco via cheatography.com/133629/cs/27343/
Insertion Sort Combinations Backtrack Pattern (cont)
void insertionSort(int arr[]) { }
int n = arr.length; }
for (int i = 1; i < n; ++i) { }
int key = arr[i];
int j = i - 1; Palindrome Backtrack Pattern
while (j >= 0 && arr[j] > key) { - Palindrome Partitioning
arr[j + 1] = arr[j]; public List<List<String>> partition(String s) {
j = j - 1; List<List<String>> list = new ArrayList<>();
} backtrack(list, new ArrayList<>(), s, 0);
arr[j + 1] = key; return list;
} }
} public void backtrack(List<List<String>> list,
List<String> tempList, String s, int start){
Combinations Backtrack Pattern if(start == s.length())
- Combination list.add(new ArrayList<>(tempList));
public List<List<Integer>> combinationSum (int[] else{
nums, int target) { for(int i = start; i < s.length(); i++){
List<List<Integer>> list = new ArrayList<>(); if(isPalindrome(s, start, i)){
Arrays.sort(nums); tempList.add(s.substring(start, i +
backtrack(list, new ArrayList<>(), nums, 1));
target, 0); backtrack(list, tempList, s, i + 1);
return list; tempList.remove(tempList.size() - 1);
} }
private void backtrack(List<List<Integer>> list, }
List<Integer> tempList, int [] nums, int remain, }
int start){ }
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<> Subsets Backtrack Pattern
(tempList)); - Subsets
else{ public List<List<Integer>> subsets(int[] nums) {
for(int i = start; i < nums.length; i++){ List<List<Integer>> list = new ArrayList<>();
tempList.add(nums[i]); Arrays.sort(nums);
// not i + 1 because we can reuse backtrack(list, new ArrayList<>(), nums, 0);
same elements return list;
backtrack(list, tempList, nums, remain
- nums[i], i);
// not i + 1 because we can reuse
same elements
tempList.remove(tempList.size() - 1);
By burcuco Published 30th March, 2021. Sponsored by CrosswordCheats.com
cheatography.com/burcuco/ Last updated 30th March, 2021. Learn to solve cryptic crosswords!
Page 5 of 7. http://crosswordcheats.com
Data Structures and Algorithms Cheat Sheet
by burcuco via cheatography.com/133629/cs/27343/
Subsets Backtrack Pattern (cont) Permutations Backtrack Pattern (cont)
} }
private void backtrack(List<List<Integer>> list, }
List<Integer> tempList, int [] nums, int start){ }
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
// skip duplicates
if(i > start && nums[i] == nums[i-1])
continue;
// skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
Permutations Backtrack Pattern
- Permutations
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list,
List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
// element already exists, skip
if(tempList.contains(nums[i])) continue;
// element already exists, skip
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
By burcuco Published 30th March, 2021. Sponsored by CrosswordCheats.com
cheatography.com/burcuco/ Last updated 30th March, 2021. Learn to solve cryptic crosswords!
Page 6 of 7. http://crosswordcheats.com
