DSA
Cheat Sheet
Arrays & Strings →
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)
Insertion: Linear array: n/a, Dynamic array: O(n
Optimized Search : Linear array: O(log n), Dynamic array:
O(log 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)
Stack/Queue/Deque →
Stack ( Last In First Out, push(val), pop(), peek() )
Queue ( First In Last Out, offer(val), poll(), peek() )
Deque ( Provides first/last, offer(val), poll(), peek() )
Heap ( Ascending Order, offer(val), poll(), peek() )
Implementation:
Stack <E> stack = new Stack();
Queue <E> queue = new Linked List();
Deque <E> deque = new Linked List();
PriorityQueue <E> pq = new PriorityQueue();
DFS & BFS Big O Notation →
DFS ( Time = O(E+V) Space = O(Height) )
BFS ( Time = O(E+V) Space = O(Length) )
V & E -> where V is the number of vertices and E is the
number of edges.
Height -> where h is the maximum height of the tree.
Length -> where l is the maximum number of nodes in a
single level.
DFS vs BFS
DFS BFS
Better when target is closer Better when target is far fro
to Source Source
Stack -> LIF Queue -> FIF
Preorder, Inorder, Postorde Level Order Searc
Searc Goes wid
Goes dee Iterativ
Recursiv Slow
Fast
Bonus {1, -1, 0, 2, -2} into map
HashMap {-1, 0, 2, 1, -2} -> any order
Linked HashMap {1, -1, 0, 2, -2} -> insertion order
TreeMap {-2, -1, 0, 1, 2} -> sorted
Set doesn't allow duplicates.
map. get or Default Value (key, default value)
BFS Implementation for Graph:
BFS Implementation for Level- order Tree Traversal:
DFS Implementation for Graph:
DFS Implementation for In-order Tree Traversal:
Dynamic Programming →
Dynamic programming is the technique of storing
repeated computations in memory, rather than
recomputing them every time you need them.
The ultimate goal of this process is to improve runtime.
Dynamic programming allows you to use more space to
take less time.
Dynamic Programming Patterns:
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(ro ute s[i-1], routes [i-2], ... , routes
[i-k]) + cost[i]
Binary Search Recursive
Binary Search Iterative
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
Bit Manipulation →
Sign Bit: 0 -> Positive, 1 -> Negative
XOR 0 ^ 0 -> 0
AND 0 & 0 -> 0
0 ^ 1 -> 1
0 & 1 -> 0
1 ^ 1 -> 0
1 & 1 -> 1
INVERT ~ 0 -> 1
OR 0 | 0 -> 0
~ 1 -> 0
0 | 1 -> 1
Bonus:
1 | 1 -> 1 Shifting
- Left Shift
0001 << 0010 (Multiply by 2)
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 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)
Quick Sort
Insertion sort
Binary Search Iterative
Binary Search Iterative
Subset backtrack pattern
Subset backtrack pattern
palindrome backtrack pattern
permutation backtrack pattern
