Essential of Data Structures and Algorithms!
|
Stores data elements based on an sequential, most commonly 0 based, index.
|
|
Time Complexity
● Indexing: Linear array: O(1), Dynamic array: O(1) ● Search: Linear array: O(n), Dynamic array: O(n) ● Optimized Search: Linear array: O(log n), Dynamic array: O(log n) ● Insertion: Linear array: n/a, Dynamic array: O(n) |
|
Bonus:
● type[] name = {val1, val2, ...} ● Arrays.sort(arr) -> O(n log(n)) ● Collections.sort(list) -> O(n log(n)) ● int digit = '4' - '0' -> 4 ● String s = String.valueOf('e') -> "e" ● (int) 'a' -> 97 (ASCII) ● new String(char[] arr) ['a','e'] -> "ae" ● (char) ('a' + 1) -> 'b' ● Character.isLetterOrDigit(char) -> true/false ● new ArrayList<>(anotherList); -> list w/ items ● StringBuilder.append(char||String) |
|
Stores data with nodes that point to other nodes.
|
|
Time Complexity
● Indexing: O(n) ● Search: O(n) ● Optimized Search: O(n) ● Append: O(1) ● Prepend: O(1) ● Insertion: O(n) |
|
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) |
|
Stack
|
Queue
|
Deque
|
Heap
|
|
Last In First Out
|
First In Last Out
|
Provides first/last
|
Ascending Order
|
|
push(val)
pop() peek() |
offer(val)
poll() peek() |
offer(val)
poll() peek() |
offer(val)
poll() peek() |
|
Time
|
Space
|
|
|
DFS
|
O(E+V)
|
O(Height)
|
|
BFS
|
O(E+V)
|
O(Length)
|
|
DFS
|
BFS
|
|
●Better when target is closer to Source.
●Stack -> LIFO ●Preorder, Inorder, Postorder Search ●Goes deep ●Recursive ●Fast |
●Better when target is far from Source.
●Queue -> FIFO ●Level Order Search ●Goes wide ●Iterative ●Slow |
public boolean **connected**(int[][] graph, int start, int end) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> toVisit = new LinkedList<>();
toVisit.enqueue(start);
while (!toVisit.isEmpty()) {
int curr = toVisit.dequeue();
if (visited.contains(curr)) **continue**;
if (curr == end) **return** true;
for (int i : graph[start]) {
toVisit.enqueue(i);
}
visited.add(curr);
}
**return** false;
}public boolean **connected**(int[][] graph, int start, int end) {
Set<Integer> visited = new HashSet<>();
**return** connected(graph, start, end, visited);
}
private boolean **connected**(int[][] graph, int start, int end, Set<Integer> visited) {
if (start == end) **return** true;
if (visited.contains(start)) **return** false;
visited.add(start);
for (int i : graph[start]) {
if (connected(graph, i, end, visited)) {
**return** true;
}
}
**return** false;
}private void **printLevelOrder**(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
print(tempNode.data + " ");
//*add left child*
if (tempNode.left != null) {
queue.offer(tempNode.left);
}
//*add right right child*
if (tempNode.right != null) {
queue.offer(tempNode.right);
}
}
}private void **inorder**(TreeNode TreeNode) {
if (TreeNode == null)
**return**;
// Traverse left
inorder(TreeNode.left);
// Traverse root
print(TreeNode.data + " ");
// Traverse right
inorder(TreeNode.right);
}|
- Minimum (Maximum) Path to Reach a Target
|
|
Approach:
Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state. Formula: routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i] |
|
- Distinct Ways
|
|
Approach:
Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state. Formula: routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k] |
|
- Merging Intervals
|
|
Approach:
Find all optimal solutions for every interval and return the best possible answer Formula: dp[i][j] = dp[i][k] + result[k] + dp[k+1][j] |
|
- DP on Strings
|
|
Approach:
Compare 2 chars of String or 2 Strings. Do whatever you do. Return. Formula: if s1[i-1] == s2[j-1] then dp[i][j] = //code. Else dp[i][j] = //code |
|
- Decision Making
|
|
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]}); |
|
Time
|
Space
|
|
|
Binary Search
|
O(log n)
|
O(1)
|
public int **binarySearch**(int search, int[] array, int start, int end) **{**
int middle = start + ((end - start) / 2);
if(end < start) {
**return** -1;
}
if (search == array[middle]) {
**return** middle;
} else if (search < array[middle]) {
**return** binarySearch(search, array, start, middle - 1);
} else {
**return** binarySearch(search, array, middle + 1, end);
}
**}**public int **binarySearch**(int target, int[] array) **{**
int start = 0;
int end = array.length - 1;
while (start <= end) {
int middle = start + ((end - start) / 2);
if (target == array[middle]) {
**return** target;
} else if (search < array[middle]) {
end = middle - 1;
} else {
start = middle + 1;
}
}
**return** -1;
**}**|
Sign Bit
|
0 -> Positive, 1 -> Negative
|
|
AND
|
0 & 0 -> 0
0 & 1 -> 0 1 & 1 -> 1 |
|
OR
|
0 | 0 -> 0
0 | 1 -> 1 1 | 1 -> 1 |
|
XOR
|
0 ^ 0 -> 0
0 ^ 1 -> 1 1 ^ 1 -> 0 |
|
INVERT
|
0 -> 1
1 -> 0 |
|
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
|
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 **mergesort**(int low, int high) **{**{{nl}} if (low < high) {{{nl}} int middle = low + (high - low) / 2;{{nl}} mergesort(low, middle);{{nl}} mergesort(middle + 1, high);{{nl}} merge(low, middle, high);{{nl}} }{{nl}} **}**
private void **merge**(int low, int middle, int high) **{**{{nl}} for (int i = low; i <= high; i++) {{{nl}} helper[i] = numbers[i];{{nl}} }{{nl}} int i = low;{{nl}} int j = middle + 1;{{nl}} int k = low;{{nl}} while (i <= middle && j <= high) {{{nl}} if (helper[i] <= helper[j]) {{{nl}} numbers[k] = helper[i];{{nl}} i++;{{nl}} } else {{{nl}} numbers[k] = helper[j];{{nl}} j++;{{nl}} }{{nl}} k++;{{nl}} }{{nl}} while (i <= middle) {{{nl}} numbers[k] = helper[i];{{nl}} k++;{{nl}} i++;{{nl}} }{{nl}} **}**{{nl}}private void **quicksort**(int low, int high) **{**{{nl}} int i = low, j = high;{{nl}} int pivot = numbers[low + (high-low)/2];{{nl}} while (i <= j) {{{nl}} while (numbers[i] < pivot) {{{nl}} i++;{{nl}} }{{nl}} while (numbers[j] > pivot) {{{nl}} j--;{{nl}} }{{nl}} if (i <= j) {{{nl}} exchange(i, j);{{nl}} i++;{{nl}} j--;{{nl}} }{{nl}} }{{nl}} if (low < j){{nl}} quicksort(low, j);{{nl}} if (i < high){{nl}} quicksort(i, high);{{nl}} **}**{{nl}}void **insertionSort**(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}**- Combination**
public List<List<Integer>> **combinationSum**(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
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<>(tempList));
else{
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
**// not i + 1 because we can reuse same elements**
backtrack(list, tempList, nums, remain - nums[i], i);
**// not i + 1 because we can reuse same elements**
tempList.remove(tempList.size() - 1);
}
}
}**- Palindrome Partitioning**
public List<List<String>> **partition**(String s) {
List<List<String>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), s, 0);
return list;
}
public void **backtrack**(List<List<String>> list, List<String> tempList, String s, int start){
if(start == s.length())
list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
tempList.add(s.substring(start, i + 1));
backtrack(list, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}
- **Subsets**
public List<List<Integer>> **subsets**(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}
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**
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);
}
}
} No comments yet.
Cheatography n. The art of mapping complex subjects into clear, instantly navigable reference guides.