BLOG TECH DEALS LEETCODE FAQ

ABOUT
PIRATE KING

LEETCODE

CHEAT SHEET

✔ Patterns

✔ Templates

PATTERNS
Big-O notations indicate the algorithm’s general time complexity

n indicates the total number of elements in the input

Input Array is Sorted

- Binary Search: O(log n) Privacy - Terms

 - Two Pointers: O(n)
BLOG TECH DEALS LEETCODE FAQ
ABOUT
PIRATE KING
Input is a Binary Tree

- DFS (Preorder, Inorder, Postorder): O(n)

- BFS (Level Order): O(n)

Input is a Binary Search Tree

- Left < Cur < Right: O(log n)

- Inorder Traversal visits the nodes in ascending (sorted) order: O(n)

Input is a Matrix/Graph

- DFS (Recursion, Stack): O(n)

- BFS (Queue): O(n)

Find the Shortest/Nearest Path/Distance in a Tree/Matrix/Graph

- BFS (non-weighted): O(n)

- Dijkstra (weighted): O(E log V)

String Concatenation

- StringBuilder: O(n) (Java, C#, etc.)

- String.join(): O(n) (Python)

Input is a Linked List

- Dummy Node

- Two Pointers: O(n)

- Fast & Slow Pointers: O(n)

Privacy - Terms
 Recomputing the Same Input

BLOG TECH DEALS LEETCODE FAQ

ABOUT
PIRATE KING
- Memoization

Recursion is Banned

- Stack

Permutations/Combinations/Subsets

- Backtracking

Find the Top/Least Kth element

- QuickSelect: O(n) average, O(n²) worst

- Heap: O(n log k)

Common Strings

- Map

- Trie

Sort

- Quick Sort: O(n log n) average, O(n²) worst

- Merge Sort: O(n log n)

- Built-in sorts: O(n log n)

Find the Smallest/Largest/Median in a Stream

- Two Heaps

Must Solve In-Place

- Swap corresponding values

Privacy - Terms
 - Store different values in the same pointer
BLOG TECH DEALS LEETCODE FAQ
ABOUT
PIRATE KING
Maximum/Minimum Subarray/Subset/Options

- Dynamic Programming

Map/Set

- Time: O(1)

- Space: O(n)

Deque

- Replaces Stack, Queue, and LinkedList

TEMPLATES

Binary Search
O(log n)

where n = size(array)

Python Java Privacy - Terms

 1 # If the target exists, returns its leftmost index. 1 // If the target exists, returns its leftmost index.
BLOG TECH DEALS LEETCODE FAQ
2

ABOUT
3
# Else,
def
returns the index of where it should be.
binarySearch(nums: List[int], target: int) -> int:
PIRATE KING 2
3
// Else, returns the index of where it should be.
int binarySearch(int[] nums, int target) {
4 l, r = 0, len(nums) 4 int l = 0, r = nums.length;
5 while l < r : 5 while (l < r) {
6 m = (l + r) // 2; 6 int m = (l + r) / 2;
7 if nums[m] < target: 7 if (nums[m] < target) l = m + 1;
8 l = m + 1; 8 else r = m;
9 else: 9 }
10 r = m; 10 return l;
11 return l; 11 }

Binary Tree Traversals

O(n)

where n = size(tree)

Python - DFS

1 def postorder(root: TreeNode) -> None:

1 def preorder(root: TreeNode) -> None: 1 def inorder(root: TreeNode) -> None:
2 if not root: return
2 if not root: return 2 if not root: return
3 postorder(root.left)
3 print(root.val) 3 inorder(root.left)
4 postorder(root.right)
4 preorder(root.left) 4 print(root.val)
5 print(root.val)
5 preorder(root.right) 5 inorder(root.right)
Privacy - Terms
BLOG TECH DEALS LEETCODE FAQ Java - DFS

ABOUT
1 void preorder(TreeNode root) { 1 PIRATE KING
void inorder(TreeNode root) { 1 void postorder(TreeNode root) {
2 if (root == null) return; 2 if (root == null) return; 2 if (root == null) return;
3 System.out.print(root.val + " "); 3 inorder(root.left); 3 postorder(root.left);
4 preorder(root.left); 4 System.out.print(root.val + " "); 4 postorder(root.right);
5 preorder(root.right); 5 inorder(root.right); 5 System.out.print(root.val + " ");
6 } 6 } 6 }

Python - BFS Java - BFS

1 def levelorder(root: TreeNode) -> None: 1 void levelorder(TreeNode root) {

2 if not root: return 2 if (root == null) return;
3 q = deque([root]) 3 Deque<TreeNode> q = new ArrayDeque<>();
4 4 q.addLast(root);
5 while q: 5 while (q.isEmpty() == false) {
6 size = len(q) 6 int size = q.size();
7 for i in range(size): 7 for (int i = 0; i < size; i++) {
8 node = q.popleft() 8 TreeNode node = q.removeFirst();
9 print(str(node.val), end = " ") 9 System.out.println(node.val + " ");
10 if node.left: 10 if (node.left != null) q.addLast(node.left);
11 q.append(node.left) 11 if (node.right != null) q.addLast(node.right);
12 if node.right: 12 }
13 q.append(node.right) 13 System.out.println();
14
14 }
15 print() 15 }

Privacy - Terms
BLOG TECH DEALS LEETCODE FAQ
Matrix Traversals
PIRATE KING
ABOUT
O(n)

where n = size(grid)

Python - DFS Java - DFS

1 def dfs(grid: List[List[int]], i: int, j: int, visited: Set[Li

1 void dfs(int[][] grid, int i, int j, boolean[][] visited) {
2 if i < 0 or j < 0 or i >= len(grid) or \
2 if (i < 0 || j < 0 || i >= grid.length ||
3 j >= len(grid[0]) or (i, j) in visited: return
3 j >= grid[0].length || visited[i][j]) return;
4
4 visited[i][j] = true;
5 visited.add((i, j))
5 dfs(grid, i + 1, j, visited);
6 dfs(grid, i + 1, j, visited)
6 dfs(grid, i - 1, j, visited);
7 dfs(grid, i - 1, j, visited)
7 dfs(grid, i, j + 1, visited);
8 dfs(grid, i, j + 1, visited)
8 dfs(grid, i, j - 1, visited);
9 dfs(grid, i, j - 1, visited)
9 }

Python - BFS Java - BFS

1 dirs = [ [0,1], [0,-1], [1,0], [-1,0] ] 1 int[][] dirs = { {0,1}, {0,-1}, {1,0}, {-1,0} };
2
2 void bfs(char[][] grid, int _i, int _j) {
3 def bfs(grid: List[List[int]], _i: int, _j: int): 3 Deque<int[]> q = new ArrayDeque<>();
4 q = deque([[_i, _j]]) 4 boolean[][] visited = new boolean[grid.length][grid[0].le
5 visited = set([(_i, _j)]) 5 q.addLast(new int[] {_i, _j});
6 6 visited[_i][_j] = true;
7 while q: 7 while (!q.isEmpty()) {
8 cur = q.popleft() 8 int[] cur = q.removeFirst();
9
9 for (int[] dir : dirs) {
10 for dir in dirs: 10 int i = cur[0] + dir[0];
Privacy - Terms
 11 i = cur[0] + dir[0] 11 int j = cur[1] + dir[1];
BLOG TECH DEALS LEETCODE
+ dir[1]FAQ
PIRATE KING
12 j = cur[1] 12 if (i < 0 || j < 0 || i >= grid.length ||

ABOUT
13 13 j >= grid[0].length || visited[i][j]) continu
14 if i < 0 or j < 0 or i >= len(grid) or \ 14 visited[i][j] = true;
15 j >= len(grid[0]) or (i, j) in visited: continue 15 q.addLast(new int[] {i, j});
16 16 }
17 visited.add((i, j)) 17 }
18 q.append([i, j]) 18 }

Graph Traversals
O(n)

where n = size(nodes)

Python - DFS Java - DFS

1 def dfs(graph: Dict[int, List[int]], cur: int, visited: Set[in 1 void dfs(Map<Integer, List<Integer>> graph, int cur, Set<Integ
2 if cur in visited: return 2 if (visited.contains(cur)) return;
3 3 visited.add(cur);
4 visited.add(cur) 4 System.out.print(cur + " ");
5 print(cur, end = " "); 5 for (int next : graph.get(cur)) {
6 6 dfs(graph, next, visited);
7 for next in graph[cur]: 7 }
8 dfs(graph, next, visited) 8 }

Privacy - Terms
 Python - BFS Java - BFS
BLOG TECH DEALS LEETCODE FAQ
ABOUT
1 def bfs(graph: Dict[int, List[int]], node: int): PIRATE KING 1 void bfs(Map<Integer, List<Integer>> graph, int node) {
2 q = deque([node]) 2 Deque<Integer> q = new ArrayDeque<>();
3 visited = set([node]) 3 Set<Integer> visited = new HashSet<>();
4
4 q.addLast(node);
5 while q: 5 visited.add(node);
6 cur = q.popleft() 6

7 7 while (q.isEmpty() == false) {

8 print(cur, end = " ") 8 int cur = q.removeFirst();
9 9 System.out.print(cur + " ");
10 for next in graph[cur]: 10 for (int next : graph.get(cur)) {
11 if next in visited: 11 if (visited.contains(next)) continue;
12 continue 12 q.addLast(next);
13 13 visited.add(next);
14 q.append(next) 14 }
15 visited.add(next) 15 }
16 16 }

String Concatenation
O(n)

where n = length(string)

Python Java Privacy - Terms

 1 # O(n^2) 1 // O(n^2)
BLOG TECH DEALS LEETCODE FAQ
PIRATE KING
2 def appendNtimesUsingStringConcat(c: str, n: int) -> str: 2 public void appendNtimesUsingStringConcat(char c, int n) {

ABOUT
3 out_str = "" 3 String str = "";
4 for i in range(n): 4 for (int i = 0; i < n; i++) {
5 out_str += c # O(s) where s = length(out_str) 5 str += c; // O(s) where s = length(str)
6 6 }
7 return out_str 7 return str;
8 8 }
9 # O(n) 9 // O(n)
10 def appendNtimesUsingStringJoin(c: str, n: int) -> str: 10 public void appendNtimesUsingStringBuilder(char c, int n) {
11 list = [] 11 StringBuilder sb = new StringBuilder();
12 for i in range(n): 12 for (int i = 0; i < n; i++) {
13 list.append(c); # O(1) 13 sb.append(c); // O(1)
14 14 }
15 return "".join(list) 15 return sb.toString();
16 16 }

Linked List
O(n)

where n = size(nodes)

Python Java

1 // before: 1-2-3-4-5-6-7 Privacy - Terms

1 # before: 1-2-3-4-5-6-7
 2 void traverse(ListNode head) {
BLOG
2 TECH
def DEALS LEETCODE
traverse(head: ListNode) ->FAQ
None:

PIRATE KING
3 if (head == null) return;
3 if not head: return
ABOUT 4 ListNode slow = head, fast = head, dummy = new ListNode(0
4
5 // puts slow in the middle
5 slow, fast, dummy = head, head, ListNode(0, head)
6 while (fast != null && fast.next != null) {
6 # puts slow in the middle
7 slow = slow.next;
7 while fast and fast.next:
8 fast = fast.next.next;
8 slow = slow.next;
9 }
9 fast = fast.next.next;
10 // d h s f
10 # d h s f
11 // after: 0-1-2-3-4-5-6-7
11 # after: 0-1-2-3-4-5-6-7
12 }
12

Merge Sort
O(n log n)

where n = size(array)

Python Java

1 def msort(nums: List[int]) -> None: 1 void msort(int[] nums) {

2 def msort_helper(nums: List[int], l: int, r: int) -> None 2 msort(nums, 0, nums.length - 1);
3 if l >= r: return 3 }
4 m = (l + r) // 2 4 void msort(int[] nums, int l, int r) {
5 msort_helper(nums, l, m) 5 if (l >= r) return;
6 msort_helper(nums, m + 1, r) 6
Privacy - Terms
 7 merge(nums, l, r) 7 int m = (l + r) / 2;
BLOG TECH DEALS LEETCODE
List[int], FAQ
PIRATE KING
8 def merge(nums: l: int, r: int) -> None: 8 msort(nums, l, m);

ABOUT
9 m = (l + r) // 2 9 msort(nums, m + 1, r);
10 i, j = l, m + 1 10 merge(nums, l, r);
11 list = [] 11 }
12 for k in range(r - l + 1): 12 void merge(int[] nums, int l, int r) {
13 if j > r or (i <= m and nums[i] < nums[j]): 13 int m = (l + r) / 2, i = l, j = m + 1;
14 list.append(nums[i]) 14 int[] arr = new int[r - l + 1];
15 i += 1 15 for (int k = 0; k < arr.length; k++) {
16 else: 16 if (j > r || (i <= m && nums[i] < nums[j])) arr[k] =
17 list.append(nums[j]) 17 else arr[k] = nums[j++];
18 j += 1 18 }
19 for k in range(len(list)): 19 for (int k = 0; k < arr.length; k++) {
20 nums[l] = list[k] 20 nums[l++] = arr[k];
21 l += 1 21 }
22 msort_helper(nums, 0, len(nums) - 1) 22 }

Quick Sort
Average: O(n log n)

Worst: O(n²)

where n = size(array)

Python Java

1 def qsort(nums: List[int]) -> None:

1 void qsort(int[] nums) {
2 def qsort_helper(nums: List[int], l: int, r: int) -> None Privacy - Terms
2 qsort(nums, 0, nums.length - 1);
 3 if l >= r: return
3 }
BLOG
TECH DEALS LEETCODE FAQ
PIRATE KING
4
4 void qsort(int[] nums, int l, int r) {
ABOUT
5 p = partition(nums, l, r)
5 if (l >= r) return;
6 qsort_helper(nums, l, p - 1)
6 int p = partition(nums, l, r);
7 qsort_helper(nums, p + 1, r)
7 qsort(nums, l, p - 1);
8

8 qsort(nums, p + 1, r);
9 def partition(nums: List[int], l: int, r: int) -> int:
9 }
10 pivot, p = nums[r], r
10 int partition(int[] nums, int l, int r) {
11

11 int pivot = nums[r];

12 i = l
12 int p = r;
13 while i < p:
13 for (int i = l; i < p; i++) {
14 if nums[i] > pivot:
14 if (nums[i] >= pivot) {
15 nums[i], nums[p - 1] = nums[p - 1], nums[i]
15 swap(nums, i, p - 1);
16 nums[p], nums[p - 1] = nums[p - 1], nums[p]
16 swap(nums, p, p - 1);
17 i -= 1
17 i--;
18 p -= 1
18 p--;
19 i += 1
19 }
20

20 }
21 return p
21 return p;
22
22 }
23 qsort_helper(nums, 0, len(nums) - 1)
23 void swap(int[] nums, int a, int b) {
24
24 int tmp = nums[a];
25
25 nums[a] = nums[b];
26
26 nums[b] = tmp;
27
27 }

Privacy - Terms
BLOG TECH DEALS LEETCODE FAQ Quick
PIRATESelect
KING
ABOUT
Average: O(n)

Worst: O(n²)

where n = size(array)

Python Java

1 def findKthLargest(self, nums: List[int], k: int) -> int: 1 public int findKthLargest(int[] nums, int k) {
2 def qselect(nums: List[int], l: int, r: int, k: int) -> N 2 return quickSelect(nums, 0, nums.length - 1, nums.length
3 p = partition(nums, l, r) 3 }
4 4 private int quickSelect(int[] nums, int l, int r, int k) {
5 if p < k: 5 int p = partition(nums, l, r);
6 return qselect(nums, p + 1, r, k) 6 if (p < k) return quickSelect(nums, p + 1, r, k);
7 if p > k: 7 if (p > k) return quickSelect(nums, l, p - 1, k);
8 return qselect(nums, l, p - 1, k) 8 return nums[p];
9 9 }
10 return nums[p] 10 private int partition(int[] nums, int l, int r) {
11
11 int pivot = nums[r];
12 def partition(nums: List[int], l: int, r: int) -> int: 12 int p = r;
13 pivot, p = nums[r], r 13 for (int i = l; i < p; i++) {
14
14 if (nums[i] > pivot) {
15 i = l 15 swap(nums, i, p - 1);
16 while i < p: 16 swap(nums, p, p - 1);
17 if nums[i] > pivot: 17 i--;
18 nums[i], nums[p - 1] = nums[p - 1], nums[i] 18 p--;
19 nums[p], nums[p - 1] = nums[p - 1], nums[p] 19 }
20 i -= 1 20 }
21 p -= 1 21 return p;
22 22 }
23 i += 1 23 private void swap(int[] nums, int a, int b) { Privacy - Terms
 24
24 int tmp = nums[a];
BLOG TECH DEALSp LEETCODE FAQ
PIRATE KING
25 return 25 nums[a] = nums[b];

ABOUT
26
26 nums[b] = tmp;
27 return qselect(nums, 0, len(nums) - 1, len(nums) - k) 27 }

Trie
O(n)

where n = length(string)

Python Java

1 class Trie {
1 class TrieNode:
2 private class TrieNode {
2 def __init__(self):
3 public boolean isWord = false
3 self.isWord = False
4 public TrieNode[] nodes = new TrieNode[26];
4 self.nodes = {}
5 }
5
6 TrieNode root = new TrieNode();
6 class Trie:
7 /** Inserts a word into the trie. */
7 def __init__(self):
8 public void insert(String word) {
8 self.root = TrieNode()
9 TrieNode cur = root;
9

10 for (int i = 0; i < word.length(); i++) {

10 # Inserts a word into the trie.
11 char c = word.charAt(i);
11 def insert(self, word: str) -> None:
12 int index = c - 'a';
12 cur = self.root;
13 if (cur.nodes[index] == null) cur.nodes[index] = - Terms
Privacy
13
 14 cur = cur.nodes[index];
14 for c in word:
BLOG TECH DEALS LEETCODE FAQ
PIRATE KING
15 }
15 if c not in cur.nodes:
ABOUT
16 cur.nodes[c] = TrieNode()
16 cur.isWord = true;
17 }
17 cur = cur.nodes[c]
18 /** Returns if the word is in the trie. */
18
19 public boolean search(String word) {
19 cur.isWord = True;
20 TrieNode cur = root;
20

21 for (int i = 0; i < word.length(); i++) {

21 # Returns if the word is in the trie
22 char c = word.charAt(i);
22 def search(self, word: str) -> bool:
23 int index = c - 'a';
23 cur = self.root
24 if (cur.nodes[index] == null) return false;
24
25 cur = cur.nodes[index];
25 for c in word:
26 }
26 if c not in cur.nodes:
27 return cur.isWord;
27 return False
28 }
28 cur = cur.nodes[c]
29 /** Returns if there is any word in the trie
29
30 that starts with the given prefix. */
30 return cur.isWord
31 public boolean startsWith(String prefix) {
31 # Returns if there is any word in the trie
32 TrieNode cur = root;
32 # that starts with the given prefix. */
33 for (int i = 0; i < prefix.length(); i++) {
33 def startsWith(self, prefix: str) -> bool:
34 char c = prefix.charAt(i);
34 cur = self.root
35 int index = c - 'a';
35
36 if (cur.nodes[index] == null) return false;
36 for c in prefix:
37 cur = cur.nodes[index];
37 if c not in cur.nodes:
38 }
38 return False
39 return true;
39 cur = cur.nodes[c]
40 }
40
41 }
41 return True

Privacy - Terms
BLOG TECH DEALS LEETCODE FAQ
ABOUT
PIRATE KING
Deque
O(1)

addFirst, addLast, removeFirst, removeLast

Python

1 # Stack 1 # Queue 1 # LinkedList

2 s = deque() 2 q = deque() 2 ll = deque()
3 s.append(1); # 1 3 q.append(1); # 1 3 ll.append(1); # 1
4 s.append(2); # 1,2 4 q.append(2); # 1,2 4 ll.append(2); # 1,2
5 s.append(3); # 1,2,3 5 q.append(3); # 1,2,3 5 ll.appendleft(0); # 0,1,2
6 s.pop(); # 1,2 6 q.popleft(); # 2,3 6 ll.pop(); # 0,1
7 s.pop(); # 1 7 q.popleft(); # 3 7 ll.popleft(); # 1

Java

1 // Stack 1 // Queue 1 // LinkedList

2 Deque<Integer> s = new ArrayDeque<>(); 2 Deque<Integer> q = new ArrayDeque<>(); 2 Deque<Integer> ll = new ArrayDeque<>();
3 s.addLast(1); // 1 3 q.addLast(1); // 1 3 ll.addLast(1); // 1
4 s.addLast(2); // 1,2 4 q.addLast(2); // 1,2 4 ll.addLast(2); // 1,2
5 s.addLast(3); // 1,2,3 5 q.addLast(3); // 1,2,3 5 ll.addFirst(0); // 0,1,2
6 s.removeLast(); // 1,2 6 q.removeFirst(); // 2,3 6 ll.removeLast(); // 0,1
7 s.removeLast(); // 1 7 q.removeFirst(); // 3 7 ll.removeFirst(); // 1

Privacy - Terms
BLOG TECH DEALS LEETCODE FAQ Back to Top
ABOUT
PIRATE KING

Subscribe

Email Address

SIGN UP

© PIRATE KING 2022

GOLDSTONE STUDIO LLC

Privacy Policy

Privacy - Terms