LeetCode Notes

Basic Data Structures

Logic categories
1. Linear: array, stack, queue, linked list
2. Non-linear: tree, graph
Linear
1. array: the most basic one
2. queue: FIFO, enqueue from back, dequeue from head
3. stack: LIFO, push from head, pop from head, peed from head
4. linked list

Non-linear

tree: DOM, XML
1. a tree is a acyclic connected graph
2. tree is recursive
binary tree
1. degree of a node is at most 2
2. all trees can be represented by binary trees
3. heap
  1. a heap is a priority queue
  2. binary heap
    1. definition:
      - heap property: each node is smaller (min heap) or larger (max heap) than its children
      - the left subtree and right subtree of each node is a binary heap
4. binary search tree
  1. definition
    - each node on left subtree is smaller than root node
    - each node on right subtree is larger than root node
    - the left subtree and right subtree of each node is a binary search tree
  2. the traversal result of a binary search tree is sorted
5. balanced binary tree
  1. AVL
  2. RBT
6. Trie tree
graph
1. directed/undirected, weighted/unweighted, cyclic/acyclic, in-degree/out-degree, path/cycle, connected(undirected)/strong connected(directed)
2. spanning tree: a tree with n nodes and n - 1 edges
  1. MST: minimum possible total edge weight
3. construct a graph
  1. adjacent matrix
  2. adjacent list
4. graph traversal
  1. if theres is cycle in a tree, you need to store which nodes have been visited
  2. DFS
  3. BFS

graph algorithm

dijkstra

shortest path, it' greedy algorithm (find shortest neighbor), it's dfs

time complexity:

O (l o g N)

import heapq

def dijkstra(graph, start, end) {
   heap = [(0, start)]
   visited = set()
   while heap:
      cost, node = heapq.heappop(heap)
      if node in visited:
         continue
      visited.add(node)
      if node == end:
         return cost
      for nbr, w in graph.adjacent(node):
         if nbr in visited:
            continue
         cur_cost = cost + w
         heapq.heappush(heap, (cur_cost, nbr))
   return -1
};

floyd-warshall

can be used to calculate dist between arbitrage two points because it save the intermediate results, while dijkstra only solves shortest path from singe start, you need a loop to solve multiple-source shortest path problem in dijkstra
it used dynamic programming rather than greedy, to it can handles negative weights

time complexity:

O (n^{3})

, space complexity:

O (n^{2})

# let graph[i][j] is the adjacent matrix of graph G

def floyd(graph, n):
   dist = [[float("inf") for _ in range(n)] for _ in range(n)]
   for i in range(n):
      for j in range(n):
         dist[i][j] = graph[i][j]
   # The outmost layer should be k
   for k in range(n):
      for i in range(n):
         for j in range(n):
            if dist[i][k] != float("inf") and dist[k][j] != float("inf") and dist[i][j] > dist[i][k] + dist[k][j]:
               dist[i][j] = dist[i][k] + dist[k][j]
   return dist

bellman-ford

can solve single source shortest path problem

based on dynamic programming, it's slower thant dijkstra algorithm, but it can handle negative weights

# let edges be a list of edges, each edge is a list [u, v, w] where u and v are vertices, and w is the weight of edge uv
# n is the number of vertices
def bellman(edges, start, n):
   dist = [float("inf") for _ in range(n)]:
   dist[start] = 0
   for _ in range(n):
      for u, v, w in edges:
         if dist[u] != float("inf") and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
   # check if there is a negative weight cycle
   for u, v, w in edges:
      if dist[u] != float("inf") and dist[u] + w < dist[v]:
         return None
   return dist

topological sort

topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering
a topological sort is possible if and only if the graph has not directed cycles, that is, if it is a directed acyclic graph(DAG), and any DAG has at least on topological ordering

Kahn algorithm

processes:
- compute in-degree of each vertex, and initialize visited vertices amount to 0
- put all vertices with in-degree 0 into a queue
- remove a vertex from the queue and then increase visited vertices amount by one, decrease in-degree of its adjacent vertices by one, if in-degree of a neighboring vertex is reduced to 0, add it to the queue, and repeat this process until the queue is empty
- if the visited vertices amount is not equal to the total amount of vertices, there is a cycle in the graph, otherwise the done

time complexity:

O (V + E)

def kahn(graph):
   indegree = [0] * len(graph.V)
   queue = collections.deque()
   res = []
   cnt = 0
   for u,v in graph.E:
      indegree[v] += 1
   for i in range(len(graph.V)):
      if indegree[i] == 0:
         queue.append(i)
   while queue:
      cur = queue.popleft()
      res.append(cur)
      cnt += 1
      for nbr in graph.adjacent(cur):
         indegree[nbr] -= 1
         if indegree[nbr] == 0:
            queue.append(nbr)
   if cnt != len(graph.V):
      return None
   return res

minimum spanning tree

a minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weigh
spanning tree and MST may not be unique

Kruskal algorithm

processes:
- create a forest F (a set of trees), where each vertex in the graph is a separate tree
- create a set S containing all the edges in the graph
- while S is nonempty and F is not yet spanning, remove an edge with minimum weight from S, if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree

time complexity:

O (E l o g E)

# This class is for union find
class DisjointSetUnion:
   def __init__(self, n):
      self.n = n
      self.rank = [1] * n
      self.f = list(range(n))
   
   def find(self, x: int) -> int:
      if self.f[x] == x:
            return x
      self.f[x] = self.find(self.f[x])
      return self.f[x]
   
   def unionSet(self, x: int, y: int) -> bool:
      fx, fy = self.find(x), self.find(y)
      if fx == fy:
            return False
      if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx
      self.rank[fx] += self.rank[fy]
      self.f[fy] = fx
      return True

class Algorithm:
   def Kruskal(self, graph):
      dsu = DisjointSetUnion(len(graph.V))
      graph.E.sort()
      ret, num = 0, 1
      for u, v, w in graph.E:
            if dsu.unionSet(u, v):
               ret += w
               num += 1
               if num == n:
                  break
      return ret

Prim algorithm

processes:
- initialize a tree with a single vertex, chosen arbitrarily from the graph
- grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree
- repeat the above step until all vertices are in the tree

time complexity:

O (E + V l o g V)

class Solution:
   def Prim(self, dist) -> int:
      n = len(dist)
      d = [float("inf")] * n
      vis = [False]  * n
      d[0] = 0
      ans = 0
      for _ in range(n):
            M = float("inf") 
            for i in range(n):
               if not vis[i] and d[i] < M:
                  node = i
                  M = d[i]
            vis[node] = True
            ans += M
            for i in range(n):
               if not vis[i]:
                  d[i] = min(d[i], dist[i][node])
      return ans

Template

Binary search, time complexity O(logN)

private int binarySearchHelper(int[] nums, target, low, high) {
   if (low > high) {
      return -1;
   }
   int mid = low + (high - low ) / 2;
   if (nums[mid] == target) {
      return mid;
   } else if (nums[mid] < target ) {
      return binarySearchHelper(nums, target, mid + 1, high);
   } else {
      return binarySearchHelper(nums, target, low, mid - 1);
   }
}

public int binarySearch(int[] nums, int target) {
   return binarySearchHelper(nums, target, 0, nums.length - 1);
}

Binary Tree traversal

PreOrder, time complexity: O(N)

// Recursive
public void preOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   System.out.println(root.data);
   preOrder(root.left);
   preOrder(root.right);

}

// Iterative, space complexity: O(N)
public void preOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   Stack<TreeNode> stack = new Stack<>();
   stack.push(root);
   while (!stack.isEmpty()) {
      TreeNode cur = stack.pop();
      System.out.println(cur.data);
      if (cur.right != null) {
         stack.push(cur.right);
      }
      if (cur.left != null) {
         stack.push(cur.left);
      }
   }

}

// Morris traversal, space complexity: O(1)
public void preOrder(TreeNode root) {
   TreeNode cur = root;
   while (cur != null) {
      if (cur.left == null) {
         System.out.println(cur.data);
         cur = cur.right;
      } else {
         TreeNode pre = cur.left;
         while (pre.right != null && pre.right != cur) {
            pre = pre.right;
         }
         if (pre.right == null) {
            System.out.println(cur.data);
            pre.right = cur;
            cur = cur.left;
         } else {
            pre.right = null;
            cur = cur.right;     
         }
      }
   }
}

InOrder, time complexity: O(N)

// Recursive
public void inOrder(TreeNode root) {
   if (root == null) {
      return;
   } 
   inOrder(root.left);
   System.out.println(root.data);
   inOrder(root.right);
}

// Iterative, space complexity: O(N)
public void inOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   Stack<TreeNode> stack = new Stack<>();
   TreeNode cur = root;
   while (cur != null || !stack.isEmpty()) {
      while (cur != null) {
         stack.push(cur);
         cur = cur.left;
      }
      cur = stack.pop();
      System.out.println(cur.data);
      cur = cur.right;
   }
}

// Morris traversal, space complexity: O(1)
public void inOrder(TreeNode root) {
   TreeNode cur = root;
   while (cur != null) {
      if (cur.left == null) {
         System.out.println(cur.data);
         cur = cur.right;
      } else {
         // find the predecessor of cur
         TreeNode pre = cur.left;
         while (pre.right != null && pre.right != cur) {
            pre = pre.right;
         }
         if (pre.right == null) {
            // If we haven't visited the predecessor before, add a link
            // so we can come back to cur
            pre.right = cur;
            cur = cur.left;
         } else {
            // If we have visited the predecessor before, then the
            // left-subtree of cur has been traversed, so we can
            // safely remove the link and print cur's data 
            pre.right = null;
            System.out.println(cur.data);
            cur = cur.right;
         }
      }
   }
}

PostOrder, time complexity: O(N)

// Recursive
public void postOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   postOrder(root.left);
   postOrder(root.right);
   System.out.println(root.data);
}

// Iterative
public void postOrder(TreeNode root) {
   TreeNode cur = root;
   TreeNode pre = null;
   Stack<TreeNode> stack = new Stack<>();      
   while(cur != null || !stack.empty()){
      while (cur != null){				
         stack.push(cur);
         cur = cur.left;
      }
      cur = stack.peek();
      if(cur.right == null || cur.right == pre){
         // If no right subtree or we have visited the right subtree
         System.out.println(cur.data);
         stack.pop();
         pre = cur;
         cur = null;
      }
      else
         // Visit the right subtree
         cur = cur.right;
   }
}

LevelOrder, time complexity: O(N)

// Iterative
public void levelOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   Queue<TreeNode> queue = new LinkedList<>();
   queue.add(root);
   while (!queue.isEmpty()) {
      TreeNode cur = queue.poll();
      System.out.println(cur.data);
      if (cur.left != null) {
         queue.add(cur.left);
      }
      if (cur.right != null) {
         queue.add(cur.right);
      }
   }
}

Height, time complexity: O(N)

Height of a node: the number of edges on the longest path from the node to a leaf

public int height(TreeNode root) {
   if (root == null) {
      return -1;
   }
   return Math.max(height(root.left), height(root.right)) + 1;
}

Binary, time complexity: O(N) (Assuming this meant "Depth")

Depth of a node: the number of edges on the path from the node to the root

public int depth(TreeNode root, TreeNode node) {
   if (root == node) {
      return 0;
   }
   return 1 + depth(root, node.parent);
}

BST

Search, time complexity: on average O(H)

public TreeNode search(TreeNode root, int data) {
   if (root == null || root.data == data) {
      return root;
   }
   if (root.data > data) {
      return search(root.left, data);
   }
   if (root.data < data) {
      return search(root.right, data);
   }
}

Minimum/Maximum time complexity: on average O(H)

public TreeNode minimum(TreeNode root) {
   TreeNode cur = root;
   while (cur.left != null) {
      cur = cur.left;
   }
   return cur;
}

public TreeNode maximum(TreeNode root) {
   TreeNode cur = root;
   while (cur.right != null) {
      cur = cur.right;
   }
   return cur;
}

Successor/Predecessor, time complexity: on average O(H)

public TreeNode successor(TreeNode node) {
   if (node.right != null) {
      return minimum(node.right);
   }
   TreeNode cur = node;
   while (cur.parent != null && cur == cur.parent.right) {
      cur = cur.parent;
   }
   return cur.parent;
}

public TreeNode predecessor(TreeNode node) {
   if (node.left != null) {
      return maximum(node.left);
   }
   TreeNode cur = node;
   while (cur.parent != null && cur == cur.parent.left) {
      cur = cur.parent;
   }
   return cur.parent;
}

Insert, time complexity: on average O(H)

// Iterative
public TreeNode insert(TreeNode root, TreeNode node) {
   TreeNode prev = null;   // prev is the parent of the inserted node
   TreeNode cur = root;   // cur is where node should be inserted
   while (cur != null) {
      prev = cur;
      if (cur.data > node.data) {
         cur = cur.left;
      } else {
         cur = cur.right;
      }
   }
   node.parent = prev;
   if (prev == null) {  // root is null, empty tree
      root = node;
   } else {
      if (prev.data > node.data) {
         prev.left = node;
      } else {
         prev.right = node;
      }
   }
   return root;
}

// Recursive
public TreeNode insert(TreeNode root, TreeNode node) {
   if (root == null) {
      root = node;
      return root;
   }
   if (root.data > node.data) {
      TreeNode left = insert(root.left, node);
      root.left = left;
      left.parent  = root;
   } else if (root.data < node.data) {
      TreeNode right = insert(root.right, node);
      root.right = right;
      right.parent = root;
   }
   return root;
}

Delete, time complexity: on average O(H)

// Iterative
public TreeNode delete(TreeNode root, TreeNode node) {
   TreeNode replace = null;
   if (node.left == null ||node.right == null) {
      replace = node;
   } else {
      replace = successor(node); 
   }
   // If replace is node, then child is the child of node or null, the following 
   // code delete node, connect parent of node and child
   // If replace is not node, then child is the child of successor of node,
   // the following code delete successor, connect its parent and child 
   TreeNode child = null;
   if (replace.left == null) {
      child = replace.right;
   } else {
      child = replace.left;
   }
   if (child != null) {
      child.parent = replace.parent;
   }
   if (replace.parent == null) {
      root = child;
   } else {
      if (replace.equals(replace.parent.left)) {
         replace.parent.left = child;
      } else {
         replace.parent.right = child;
      }
   }
   if (!replace.equals(node)) {
      node.data = replace.data;
   }
   return root;
}

// Recursive
public TreeNode delete (TreeNode root, TreeNode node) {
   if (root == null) {
      return null;
   }
   if (root.data < node.data) {
      TreeNode right = delete(root.right, node);
      root.right = right;
      if (right != null) {
         right.parent = root;
      }
   } else if (root.data > node.data) {
      TreeNode left = delete(root.left, node);
      root.left = left;
      if (left != null) {
         left.parent = root;
      }
   } else {
      if (root.left == null) {
         return root.right;
      } else if (root.right == null) {
         return root.left;
      }
      TreeNode successor = minimum(root.right);
      root.data = successor.data;
      root.right = delete(root.right, successor);
   }
   return root;
}

Sorting

Bubble sorting, time complexity: O(N^2)

public void bubbleSort(int[] arr) {
   int n = arr.length;
   for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
         if (arr[j] > arr[j + 1]) {
            int tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
         }
      }
   }
}

public void bubbleSort(int[] a) {
   boolean disSwap = true;
   while (disSwap) {
      disSwap = false;
      for (int i = 0; i < a.length - 1; i++) {
         if (a[i] > a[i + 1]) {
            int tmp = a[i + 1];
            a[i + 1] = a[i];
            a[i] = tmp;
            disSwap = true;
         }
      }
   }
}

Insertion sort, time complexity: O(N^2)

public void insertionSort(int[] a) {
   int n = a.length;
   for (int i = 1; i < n; i++) {
      int key = a[i];
      int j = i;
      while(j > 0 && a[j] > key) { // Error in original HTML, should be a[j-1] > key
         a[j] = a[j-1];             // Error in original HTML, should be a[j] = a[j-1]
         j = j - 1;
         }
      a[j] = key;                 // Error in original HTML, should be a[j] = key
   }
}
// Corrected version from typical insertion sort:
// public void insertionSort(int[] a) {
//    int n = a.length;
//    for (int i = 1; i < n; i++) {
//       int key = a[i];
//       int j = i - 1;
//       while(j >= 0 && a[j] > key) {
//          a[j + 1] = a[j];
//          j = j - 1;
//       }
//       a[j + 1] = key;
//    }
// }

Selection sort, time complexity: O(N^2)

public void selectionSort(int[] a) {
   int n = a.length;
   for (int i = 0; i < n - 1; i++) {
      int min = i;
      for (int j = i + 1; j < n; j++) {
         if(a[j] < a[min]) {
            min = j;
         }
      }
      int tmp = a[i];
      a[i] = a[min];
      a[min] = tmp; // Error in original HTML: a[min] = tmp;] - removed trailing ]
   }
}

Shell sort, time complexity: O(N^2)

public void shellSort(int[] arr) {
   int n = arr.length;
   for (int gap = n / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < n; i++) {
      int key = arr[i]; // Error in original HTML: arr[gap]
      int j = i;
      while (j >= gap && arr[j - gap] > key) { // Error in original HTML: arr[j] > key and j-gap logic
         arr[j] = arr[j - gap]; // Error in original HTML: arr[j+gap] = arr[j]
         j = j - gap;
      }
      arr[j] = key; // Error in original HTML: arr[j+gap] = key
      }
   }
}
// Corrected version from typical shell sort:
// public void shellSort(int[] arr) {
//    int n = arr.length;
//    for (int gap = n / 2; gap > 0; gap /= 2) {
//       for (int i = gap; i < n; i++) {
//          int key = arr[i];
//          int j = i;
//          while (j >= gap && arr[j - gap] > key) {
//             arr[j] = arr[j - gap];
//             j -= gap;
//          }
//          arr[j] = key;
//       }
//    }
// }

Merge sort, time complexity: O(NlogN)

 private void merge(int[] arr, int lo, int mid, int hi) {
    int n1 = mid - lo + 1;
    int n2 = hi - mid;
    int[] L = new int[n1]; // L is arr[lo, ..., mid]
    int[] R = new int[n2]; // R is arr[mid + 1, ..., hi]
    for (int i = 0; i < n1; i++) {
       L[i] = arr[lo + i];
    }
    for (int j = 0; j < n2; j++) {
       R[j] = arr[mid + 1 + j];
    }
    int i = 0;
    int j = 0;
    int k = lo;
    while (i < n1 && j < n2) {
       if (L[i] <= R[j]) {
          arr[k] = L[i];
          i += 1;
       } else {
          arr[k] = R[j];
          j += 1;
       }
       k += 1;
    }
    while (i < n1) {
       arr[k] = L[i];
       i += 1;
       k += 1;
    }
    while (j < n2) {
       arr[k] = R[j];
       j += 1;
       k += 1;
    }
 }

private void mergeSortInner(int[] arr, int lo, int hi) { // Error in HTML: mergeSortInner(int arr, ...)
  if (lo >= hi) {
    return;
  }
  int mid = lo + (hi - lo) / 2;
  mergeSortInner(arr, lo, mid);
  mergeSortInner(arr, mid + 1 , hi);
  merge(arr, lo, mid, hi);
}

public void mergeSort(int[] arr) {
  int n = arr.length;
  mergeSortInner(arr, 0, n - 1); // Error in HTML: mergeSortHelper
}

Quick sort, time complexity: O(NlogN)

private int partition(int[] arr, int lo, int hi) { // Error in HTML: void partition(...)
   int x = arr[lo];
   int i = lo;
   for (int j = lo + 1; j <= hi; j++) {
      if (arr[j] <= x) {
         i += 1;
         int tmp = arr[i];
         arr[i] = arr[j];
         arr[j] = tmp; // Error in HTML: arr[j] = arr[i]
      }
   }
   int tmp = arr[i];
   arr[i] = arr[lo];
   arr[lo] = tmp;
   return i;
}

private void quickSortInner(int[] arr, int lo, int hi) {
   if (lo >= hi) {
      return;
   }
   int x = partition(arr, lo, hi);
   quickSortInner(arr, lo, x - 1);
   quickSortInner(arr, x + 1, hi);
}

public void quickSort(int[] arr) {
   int n = arr.length;
   quickSortInner(arr, 0, n - 1);
}

Heap

Max heap implementation with a 0-indexed array with length n

Parent, time complexity:

O (1)

1
2
3

public int parent(int index) {
   return (index - 1) / 2;
}

Left child, time complexity:

O (1)

public int leftChild(int index) {
   if (2 * index + 1 >= n) { // n needs to be defined (class member or passed)
      throw new IndexOutOfBoundsException();
   }
   return 2 * index + 1;
}

Right child, time complexity:

O (1)

public int rightChild(int index) {
   if (2 * index + 2 >= n) { // n needs to be defined
      throw new IndexOutOfBoundsException();
   }
   return 2 * index + 2;
}

Heapify-up, time complexity:

O (l o g N)

public void heapifyUp(int[] arr, int index) {
   while (index > 0 && arr[parent(index)] < arr[index]) { // Assumes parent() is accessible
      int tmp = arr[parent(index)];
      arr[parent(index)] = arr[index];
      arr[index] = tmp;
      index = parent(index);
   }
}

Heapify-down, time complexity:

O (l o g N)

public void heapifyDown(int[] arr, int n, int index) {
   int left = leftChild(index); // Assumes leftChild() is accessible and uses 'n' correctly
   int right = rightChild(index); // Assumes rightChild() is accessible and uses 'n' correctly
   int largest = index;
   if (left < n && arr[left] > arr[largest]) {
      largest = left;
   }
   if (right < n && arr[right] > arr[largest]) {
      largest = right;
   }
   if (largest != index) {
      int tmp = arr[index];
      arr[index] = arr[largest];
      arr[largest] = tmp;
      heapifyDown(arr, n, largest);
   }
}

Build-max-heap from array, time complexity:

O (N)

Consider

n = 2^{h + 1} - 1

, which is a heap with

n

nodes and height

h

(root at level 0). At level

h

, there are

2^{h}

nodes but no shift down is needed, at level

h - 1

, there are

2^{h - 1}

nodes, and at most one shift down for each node, so the total is

T (n) = \sum_{j = 0}^{h} j 2^{h - j} \leq \sum_{j = 0}^{\infty} j 2^{h - j} = n + 1 = O (n)

public void buildMaxHeap(int[] arr) {
   n = arr.length; // n should be a class member or handled consistently
   for (int i = n / 2 - 1; i >= 0; i--) {
      heapifyDown(arr, n, i); // Error in HTML: heapifyDown(arr, i) - n is needed
   }
}

Insert, time complexity:

O (N l o g N)

(This is actually O(logN) for inserting one item into an existing heap, or O(NlogN) for building a heap by N insertions)

public void insert(int[] arr, int item) { // Error in HTML: (int arr, int item)
   heapSize += 1; // heapSize needs to be defined (class member)
   int index = heapSize - 1;
   // insert item at then end, then heapify up
   arr[index] = item;
   heapifyUp(arr, index); // Assumes heapifyUp is accessible
}

Delete max, time complexity:

O (N l o g N)

(This is actually O(logN) for deleting max from an existing heap)

public int deleteMin(int[] arr, int item) { // Error in HTML: (int arr, int item), method name suggests min but it's max heap
   int max = arr[0];
   // swap the maximum with the last one, then heapify down
   arr[0] = arr[heapSize - 1]; // heapSize needs to be defined
   heapSize -= 1;
   heapifyDown(arr, heapSize, 0); // Assumes heapifyDown is accessible
   return max;
}

Heap-sort, time complexity:

O (N l o g N)

public void heapSort(int[] arr) { // Error in HTML: public heapSort(...)
   // build a max heap
   buildMaxHeap(arr); // Assumes buildMaxHeap is accessible
   int n_orig = arr.length; // Store original length if heapSize is modified
   for (int i = n_orig - 1; i > 0; i--) {
      // swap the largest to the last one, reduce heap size, then heapify down
      int tmp = arr[0];
      arr[0] = arr[i];
      arr[i] = tmp;
      heapifyDown(arr, i, 0); // Error in HTML: heapifyDown(arr, i - 1, 0) - 'i' is the new size
   }
}

Graph

BFS, time complexity:

O (V + E)

public void bfs(Graph G, int s) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   Queue<Integer> queue = new LinkedList<Integer>();
   queue.add(s);
   visited[s] = true;
   while (!queue.isEmpty()) {
      int v = queue.poll();
      // do something with v
      for (int w: G.adj(v)) {
         if (!visited[w]) {
            queue.add(w);
            visited[w] = true;
         }
      }
   }
}

Dijkstra, time complexity:

O ((V + E) l o g V)

with PriorityQueue,

O (V^{2})

with array

 public int[] dijkstra(Graph G, int src) { // Error in HTML: dijkstra(G, int src)
   int[] dist = new int[G.V()];
   // prev[i] is the previous vertex of vertex i in the shortest path from src to i
   // path from src to i is prev[i] -> prev[prev[i]] -> ... -> src
   int[] prev = new int[G.V()];
   for (int i = 0; i < G.V(); i++) {
     dist[i] = Integer.MAX_VALUE;
     prev[i] = -1;
   }
   dist[src] = 0;
   // prev[i] = -1; // Error in HTML: prev[src] should likely be -1 or self, or this line is redundant with loop
   PriorityQueue<Integer> pq = new PriorityQueue<Integer>(G.V(), new Comparator<Integer>() {
     public int compare(Integer a, Integer b) {
       return dist[a] - dist[b];
     }
   });
   for (int i = 0; i < G.V(); i++) {
     pq.add(i); // Error in HTML: pq.enqueue(i, dist[i]); -> PriorityQueue uses add, and sorts based on comparator
   }
   while (!pq.isEmpty()) { // Error in HTML: pq.isEmpty()
     int u = pq.remove();
     for(int v: G.adj(u)) {
       if (dist[v] > dist[u] + G.weight(u, v)) { // Assumes G.weight(u,v)
         dist[v] = dist[u] + G.weight(u, v);
         prev[v] = u;
         // For PQ to re-prioritize, you'd typically remove and re-add 'v' if it's already in.
         // A common way is to allow duplicates and pick the one with min distance,
         // or use a structure that supports decrease-key.
         // Simple PQs in Java don't directly support decrease-key well.
         // So, this part might need more context on the PQ implementation.
         // If using Java's built-in PQ, you might just add a new entry:
         // pq.remove(v); // if present
         // pq.add(v); 
         // Or, more simply, just add and let the check `if (dist[v] > ...)` handle outdated entries later.
         // For this simple conversion, I'll assume the logic is mostly correct for a conceptual PQ.
       }
     }
   }
   return dist;
}

DFS, time complexity:

O (V + E)

// iterative
public void dfs(Graph G, int s) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   Stack<Integer> stack = new Stack<Integer>();
   stack.push(s);
   // visited[s] = true; // Often marked when popped or pushed, depends on style
   while (!stack.isEmpty()) {
      int v = stack.pop();
      if (!visited[v]) { // Process only if not visited
          visited[v] = true;
          // do something with v
          // Add neighbors in reverse order if you want to mimic recursive DFS visit order
          List<Integer> neighbors = G.adj(v); // Assuming adj returns a list
          for (int i = neighbors.size() - 1; i >= 0; i--) {
              int w = neighbors.get(i);
              if (!visited[w]) {
                 stack.push(w);
              }
          }
      }
   }  
}

// recursive
public void dfs(Graph G, int s) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   dfs(G, s, visited);
}
private void dfs(Graph G, int v, boolean[] visited) {
   visited[v] = true;
   // do something with v (usually here in recursive)
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         dfs(G, w, visited);
      }
   }
}

Find cycle in undirected graph, time complexity:

O (V + E)

Idea: if we can reach w from v in different ways, then there must be a cycle

public boolean hasCycle(Graph G) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   for (int s = 0; s < G.V(); s++) { // Error in HTML: i < G.V()
      if (!visited[s]) {
         if (hasCycle(G, s, -1, visited)) { // Parent of start node is -1 (or some invalid node)
            return true;
         }
      }
   }
   return false;
}

private boolean hasCycle(Graph G, int v, int u, boolean[] visited) { // u is parent
   visited[v] = true;
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         if (hasCycle(G, w, v, visited)) return true; // Propagate true
      } else if (w != u) { // Visited and not parent
         return true;
      }
   }
   return false;
}

Find cycle in directed graph, time complexity:

O (V + E)

public boolean hasCycle(Graph G) {
   boolean[] visited = new boolean[G.V()];
   boolean[] onStack = new boolean[G.V()]; // recursion stack
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
      onStack[i] = false;
   }
   for (int i = 0; i < G.V(); i++) { // Error in HTML: G.B()
      if (!visited[i]) {
         if (hasCycle(G, i, visited, onStack)) { // Removed u (parent), not needed for directed cycle with onStack
            return true;
         }
      }
   }
   return false;
}

private boolean hasCycle(Graph G, int v, boolean[] visited, boolean[] onStack) { // Removed u
   visited[v] = true;
   onStack[v] = true;
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         if (hasCycle(G, w, visited, onStack)) {
            return true;
         }
      } else if (onStack[w]) { // Found a back edge to a node on current recursion stack
         return true;
      }
   }
   onStack[v] = false; // Remove from recursion stack before returning
   return false;
}

Find SCC in directed graphs, time complexity:

O (V + E)

(Kosaraju's or Tarjan's, this looks like a simpler connected components for undirected or wrongly applied DFS for SCC)

// This is a standard DFS-based connected components algorithm,
// NOT for Strongly Connected Components in a DIRECTED graph.
// For SCC, you'd typically use Kosaraju's or Tarjan's algorithm.
// Assuming it was intended as a general component counter for an undirected graph, or a misremembered SCC approach.
public int scc(Graph G) { // Method name implies SCC
   boolean[] visited = new boolean[G.V()];
   int[] id = new int[G.V()]; // component id for each vertex
   int count = 0; // number of components
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
      id[i] = -1; // Initialize component id
   }
   for (int i = 0; i < G.V(); i++) {
      if (!visited[i]) {
         dfs_scc(G, i, visited, id, count); // Changed method name to avoid conflict
         count += 1;
      }
   }
   return count;
}

private void dfs_scc(Graph G, int v, boolean[] visited, int[] id, int current_component_id) {
   visited[v] = true;
   id[v] = current_component_id;
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         dfs_scc(G, w, visited, id, current_component_id);
      }
   }
}