Sorting, searching, dynamic programing, and graph algorithms form the backbone of competitive programming. This article presents a curated list of such patterns, each accompanied by a concise Java implementation. The examples draw inspiration from the ACwing problem set, covering topics from basic sorting to advanced combinatorial mathematics.

Basic Algorithms

Sorting

Quick Sort (mid-point pivot)

The array is partitioned around a pivot chosen from the middle index, and then recursively sorted.

void quickSort(int[] arr, int l, int r) {
  if (l >= r) return;
  int pivot = arr[(l + r) >> 1];
  int i = l - 1, j = r + 1;
  while (i < j) {
    do i++; while (arr[i] < pivot);
    do j--; while (arr[j] > pivot);
    if (i < j) swap(arr, i, j);
  }
  quickSort(arr, l, j);
  quickSort(arr, j + 1, r);
}
void swap(int[] arr, int x, int y) { int t = arr[x]; arr[x] = arr[y]; arr[y] = t; }

Merge Sort and Inversion Count

Merge sort can be extended to count the number of inversions.

long invCount(int[] arr, int l, int r, int[] tmp) {
  if (l >= r) return 0;
  int m = (l + r) >> 1;
  long left = invCount(arr, l, m, tmp);
  long right = invCount(arr, m + 1, r, tmp);
  return left + right + merge(arr, l, m, r, tmp);
}
long merge(int[] arr, int l, int m, int r, int[] tmp) {
  int i = l, j = m + 1, k = l;
  long inv = 0;
  while (i <= m && j <= r) {
    if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
    else { tmp[k++] = arr[j++]; inv += (m - i + 1); }
  }
  while (i <= m) tmp[k++] = arr[i++];
  while (j <= r) tmp[k++] = arr[j++];
  for (i = l; i <= r; i++) arr[i] = tmp[i];
  return inv;
}

Binary Search

Integer boundaries and floating-point roots both rely on a precise two-pointer approach.

int lowerBound(int[] arr, int target) {
  int l = 0, r = arr.length - 1;
  while (l < r) {
    int m = (l + r) >> 1;
    if (arr[m] >= target) r = m;
    else l = m + 1;
  }
  return arr[l] == target ? l : -1;
}
double cubeRoot(double n) {
  double l = -100.0, r = 100.0;
  while (r - l > 1e-8) {
    double m = (l + r) / 2;
    if (m * m * m >= n) r = m;
    else l = m;
  }
  return l;
}

Prefix Sum and Difference Arrays

Efficient range updates and queries are achieved through prefix sums in 1D and 2D.

// 1D prefix
int[] pref = new int[n + 1];
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
int rangeSum = pref[r] - pref[l - 1];

// 2D prefix
int[][] pref2 = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++)
  for (int j = 1; j <= m; j++)
    pref2[i][j] = pref2[i - 1][j] + pref2[i][j - 1] - pref2[i - 1][j - 1] + mat[i][j];
int sum = pref2[x2][y2] - pref2[x1 - 1][y2] - pref2[x2][y1 - 1] + pref2[x1 - 1][y1 - 1];

// Difference array for range add
int[] diff = new int[n + 2];
void addRange(int l, int r, int v) { diff[l] += v; diff[r + 1] -= v; }
for (int i = 1; i <= n; i++) arr[i] = diff[i] + arr[i - 1];

Two Pointers

// Longest substring without repeating characters
int[] cnt = new int[1000000];
int maxLen = 0;
for (int i = 0, j = 0; i < arr.length; i++) {
  cnt[arr[i]]++;
  while (j <= i && cnt[arr[i]] > 1) cnt[arr[j++]]--;
  maxLen = Math.max(maxLen, i - j + 1);
}

Bit Manipulation

int numberOfOnes(int x) {
  int c = 0;
  while (x > 0) { x -= x & -x; c++; }
  return c;
}

Coordinate Compression

Map sparse values to consecutive indices using binary search or a hash map.

// After sorting unique sorted array 'pos', map original coordinate to compressed index
int findCompressedIndex(int[] pos, int len, int val) {
  int l = 0, r = len - 1;
  while (l < r) {
    int m = (l + r) >> 1;
    if (pos[m] >= val) r = m;
    else l = m + 1;
  }
  return r + 1; // 1-based
}

Interval Merging

int[][] intervals; // sorted by left endpoint
List<int[]> merged = new ArrayList<>();
int st = intervals[0][0], ed = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
  if (intervals[i][0] > ed) {
    merged.add(new int[]{st, ed});
    st = intervals[i][0];
    ed = intervals[i][1];
  } else ed = Math.max(ed, intervals[i][1]);
}
merged.add(new int[]{st, ed});

Data Structures

Singly and Doubly Linked List (array simulation)

class SinglyList {
  int[] e = new int[100010], ne = new int[100010];
  int idx = 1; // head is at index 0
  void insertHead(int v) { e[idx] = v; ne[idx] = ne[0]; ne[0] = idx++; }
  void insertAfter(int k, int v) { e[idx] = v; ne[idx] = ne[k]; ne[k] = idx++; }
  void remove(int k) { ne[k] = ne[ne[k]]; }
}

Stack (array simulation)

int[] stk = new int[100010];
int tp = 0;
void push(int v) { stk[tp++] = v; }
int pop() { return stk[--tp]; }
int peek() { return stk[tp - 1]; }
boolean isEmpty() { return tp == 0; }

Monotonic Stack and Queue

Find the first smaller element on the left:

int[] stk = new int[n];
int tp = 0;
for (int i = 0; i < n; i++) {
  while (tp > 0 && arr[stk[tp - 1]] >= arr[i]) tp--;
  int leftSmaller = tp == 0 ? -1 : arr[stk[tp - 1]];
  stk[tp++] = i;
}

Sliding window maximum:

int[] q = new int[n];
int head = -1, tail = 0;
for (int i = 0; i < n; i++) {
  if (tail <= head && q[tail] <= i - k) tail++;
  while (tail <= head && arr[q[head]] <= arr[i]) head--;
  q[++head] = i;
  if (i >= k - 1) res[i - k + 1] = arr[q[tail]];
}

KMP Pattern Matching

int[] buildNext(String p) {
  int m = p.length();
  int[] next = new int[m + 1];
  for (int i = 2, j = 0; i <= m; i++) {
    while (j > 0 && p.charAt(j) != p.charAt(i - 1)) j = next[j];
    if (p.charAt(j) == p.charAt(i - 1)) j++;
    next[i] = j;
  }
  return next;
}
List<Integer> kmp(String s, String p) {
  List<Integer> ans = new ArrayList<>();
  int[] next = buildNext(p);
  int n = s.length(), m = p.length();
  for (int i = 1, j = 0; i <= n; i++) {
    while (j > 0 && p.charAt(j) != s.charAt(i - 1)) j = next[j];
    if (p.charAt(j) == s.charAt(i - 1)) j++;
    if (j == m) { ans.add(i - m); j = next[j]; }
  }
  return ans;
}

Trie

class Trie {
  int[][] son = new int[100010][26];
  int[] cnt = new int[100010];
  int idx = 0;
  void insert(String s) {
    int p = 0;
    for (char c : s.toCharArray()) {
      int u = c - 'a';
      if (son[p][u] == 0) son[p][u] = ++idx;
      p = son[p][u];
    }
    cnt[p]++;
  }
  int query(String s) {
    int p = 0;
    for (char c : s.toCharArray()) {
      int u = c - 'a';
      if (son[p][u] == 0) return 0;
      p = son[p][u];
    }
    return cnt[p];
  }
}

Disojint Set Union (Union-Find)

class DSU {
  int[] parent, size;
  DSU(int n) {
    parent = new int[n]; size = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
  }
  int find(int x) {
    int root = x;
    while (root != parent[root]) root = parent[root];
    while (x != parent[x]) { int nxt = parent[x]; parent[x] = root; x = nxt; }
    return root;
  }
  void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) { parent[rb] = ra; size[ra] += size[rb]; }
  }
  int getSize(int x) { return size[find(x)]; }
}

Heap (array simulation)

int[] heap = new int[100010];
int sz = 0;
void down(int u) {
  int t = u;
  if (u * 2 <= sz && heap[u * 2] < heap[t]) t = u * 2;
  if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
  if (t != u) { swap(u, t); down(t); }
}
void build() { for (int i = sz / 2; i >= 1; i--) down(i); }
int pop() {
  int v = heap[1];
  heap[1] = heap[sz--];
  down(1);
  return v;
}

String Hashing

int P = 131;
long[] h, p;
void init(char[] s) {
  int n = s.length;
  h = new long[n + 1]; p = new long[n + 1];
  p[0] = 1;
  for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + s[i - 1];
  }
}
long getHash(int l, int r) { // 1-indexed
  return h[r] - h[l - 1] * p[r - l + 1];
}

Graph and Search

DFS and BFS

Classic DFS for permutations:

boolean[] used = new boolean[n];
int[] cur = new int[n];
void dfs(int pos)
  if (pos == n) { process(cur); return; }
  for (int i = 1; i <= n; i++) {
    if (!used[i]) { used[i] = true; cur[pos] = i; dfs(pos + 1); used[i] = false; }
  }
}

BFS for shortest path in a grid:

int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
Queue<int[]> q = new ArrayDeque<>();
boolean[][] vis = new boolean[n][m];
q.offer(new int[]{0,0,0}); vis[0][0] = true;
while (!q.isEmpty()) {
  int[] cur = q.poll();
  int r = cur[0], c = cur[1], step = cur[2];
  if (r == n - 1 && c == m - 1) { ans = step; break; }
  for (int[] d : dir) {
    int nr = r + d[0], nc = c + d[1];
    if (nr >= 0 && nr < n && nc >= 0 && nc < m && !vis[nr][nc] && grid[nr][nc] == 0) {
      vis[nr][nc] = true;
      q.offer(new int[]{nr, nc, step + 1});
    }
  }
}

Topological Sort

int[] indeg = new int[n];
List<Integer>[] g = new ArrayList[n];
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
  int u = q.poll(); order.add(u);
  for (int v : g[u]) if (--indeg[v] == 0) q.offer(v);
}
if (order.size() != n) // cycle exists

Shortest Paths

Dijkstra (naive O(n²) for dense graphs)

int[] dist = new int[n];
boolean[] vis = new boolean[n];
Arrays.fill(dist, INF); dist[src] = 0;
for (int i = 0; i < n; i++) {
  int t = -1;
  for (int j = 0; j < n; j++) if (!vis[j] && (t == -1 || dist[j] < dist[t])) t = j;
  if (dist[t] == INF) break;
  vis[t] = true;
  for (int j = 0; j < n; j++) if (g[t][j] != INF) dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}

Dijkstra with heap (O(m log n))

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
int[] dist = new int[n]; Arrays.fill(dist, INF);
dist[src] = 0; pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
  int[] top = pq.poll();
  int d = top[0], u = top[1];
  if (d > dist[u]) continue;
  for (int[] e : adj[u]) {
    int v = e[0], w = e[1];
    if (dist[v] > d + w) {
      dist[v] = d + w;
      pq.offer(new int[]{dist[v], v});
    }
  }
}

Bellman-Ford (k-edges restriction)

int[] dist = new int[n]; Arrays.fill(dist, INF); dist[src] = 0;
for (int i = 0; i < k; i++) {
  int[] backup = dist.clone();
  for (int[] e : edges) {
    int a = e[0], b = e[1], w = e[2];
    if (backup[a] != INF) dist[b] = Math.min(dist[b], backup[a] + w);
  }
}

SPFA

int[] dist = new int[n]; boolean[] inQ = new boolean[n];
Arrays.fill(dist, INF); dist[src] = 0;
Queue<Integer> q = new ArrayDeque<>(); q.offer(src); inQ[src] = true;
while (!q.isEmpty()) {
  int u = q.poll(); inQ[u] = false;
  for (int[] e : adj[u]) {
    int v = e[0], w = e[1];
    if (dist[v] > dist[u] + w) {
      dist[v] = dist[u] + w;
      if (!inQ[v]) { q.offer(v); inQ[v] = true; }
    }
  }
}

Floyd-Warshall (all-pair)

int[][] d = new int[n][n]; // init with adjacency matrix, diagonal 0, missing edges INF
for (int k = 0; k < n; k++)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (d[i][k] != INF && d[k][j] != INF) d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);

Minimum Spanning Tree

Prim (O(n²)):

int[] dist = new int[n]; Arrays.fill(dist, INF); dist[0] = 0;
boolean[] inTree = new boolean[n];
int total = 0;
for (int i = 0; i < n; i++) {
  int t = -1;
  for (int j = 0; j < n; j++) if (!inTree[j] && (t == -1 || dist[j] < dist[t])) t = j;
  if (dist[t] == INF) { total = INF; break; } // no MST
  inTree[t] = true; total += dist[t];
  for (int j = 0; j < n; j++) if (!inTree[j] && g[t][j] != INF) dist[j] = Math.min(dist[j], g[t][j]);
}

Kruskal:

DSU dsu = new DSU(n);
int res = 0, cnt = 0;
Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
for (int[] e : edges) {
  int a = e[0], b = e[1], w = e[2];
  if (dsu.find(a) != dsu.find(b)) {
    dsu.union(a, b); res += w; cnt++;
  }
}
if (cnt != n - 1) // no MST

Bipartite Graph Matching (Hungarian Algorithm)

int[] match = new int[m]; // boy -> girl mapping
Arrays.fill(match, -1);
boolean[] vis = new boolean[m];
int ans = 0;
for (int b = 0; b < n; b++) {
  Arrays.fill(vis, false);
  if (dfs(b, match, vis, adj)) ans++;
}
boolean dfs(int b, int[] match, boolean[] vis, List<Integer>[] adj) {
  for (int g : adj[b]) {
    if (vis[g]) continue;
    vis[g] = true;
    if (match[g] == -1 || dfs(match[g], match, vis, adj)) {
      match[g] = b;
      return true;
    }
  }
  return false;
}

Mathematics

Primes

Trial division for primality:

boolean isPrime(int x) {
  if (x < 2) return false;
  for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
  return true;
}

Sieve (linear) to count primes up to n:

List<Integer> primes = new ArrayList<>();
boolean[] comp = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
  if (!comp[i]) primes.add(i);
  for (int j = 0; primes.get(j) * i <= n; j++) {
    comp[primes.get(j) * i] = true;
    if (i % primes.get(j) == 0) break;
  }
}

Divisors and GCD

List<Integer> divisors(int n) {
  List<Integer> res = new ArrayList<>();
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.add(i);
      if (i != n / i) res.add(n / i);
    }
  }
  return res;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

Euler's Totient Function

int phi(int n) {
  int res = n;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      res = res / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) res = res / n * (n - 1);
  return res;
}

Fast Exponentiation and Modular Inverse

long powMod(long a, long b, long m) {
  long res = 1;
  while (b > 0) {
    if ((b & 1) == 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long modInv(long a, long p) { return powMod(a, p - 2, p); } // p prime

Extended Euclidean Algorithm

int[] exgcd(int a, int b) {
  if (b == 0) return new int[]{1, 0, a};
  int[] res = exgcd(b, a % b);
  int x = res[0], y = res[1], g = res[2];
  return new int[]{y, x - a / b * y, g};
}

Combinatorics (Binomial Coefficients)

long[][] C = new long[2001][2001];
for (int i = 0; i <= 2000; i++) {
  for (int j = 0; j <= i; j++) {
    C[i][j] = (j == 0) ? 1 : (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
}

Dynamic Programming

Knapsack Models

0-1 knapsack:

int[] dp = new int[V + 1];
for (int i = 0; i < N; i++)
  for (int v = V; v >= w[i]; v--)
    dp[v] = Math.max(dp[v], dp[v - w[i]] + v[i]);

Complete knapsack:

for (int i = 0; i < N; i++)
  for (int v = w[i]; v <= V; v++)
    dp[v] = Math.max(dp[v], dp[v - w[i]] + v[i]);

Group knapsack:

for (int i = 0; i < N; i++) // groups
  for (int v = V; v >= 0; v--)
    for (int k = 0; k < group[i].length; k++)
      if (v >= gvol[i][k]) dp[v] = Math.max(dp[v], dp[v - gvol[i][k]] + gval[i][k]);

Linear and Interval DP

Longest Increasing Subsequence:

int[] dp = new int[n]; Arrays.fill(dp, 1);
int ans = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < i; j++)
    if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
  ans = Math.max(ans, dp[i]);
}

Stone merging (interval DP):

int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++)
  for (int l = 1; l + len - 1 <= n; l++) {
    int r = l + len - 1;
    dp[l][r] = INF;
    for (int k = l; k < r; k++)
      dp[l][r] = Math.min(dp[l][r], dp[l][k] + dp[k + 1][r] + pref[r] - pref[l - 1]);
  }

State Compression DP

Hamilton shortest path:

int[][] dp = new int[n][1 << n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[0][1] = 0;
for (int mask = 0; mask < (1 << n); mask++)
  for (int v = 0; v < n; v++)
    if ((mask >> v & 1) == 1)
      for (int u = 0; u < n; u++)
        if ((mask >> u & 1) == 1)
          dp[v][mask] = Math.min(dp[v][mask], dp[u][mask ^ (1 << v)] + w[u][v]);

Tree DP (party without boss)

int[][] dp = new int[n + 1][2];
void dfs(int u, int parent) {
  dp[u][1] = happy[u];
  for (int v : tree[u]) {
    if (v == parent) continue;
    dfs(v, u);
    dp[u][0] += Math.max(dp[v][0], dp[v][1]);
    dp[u][1] += dp[v][0];
  }
}

Memorized Search (skiing)

int[][] mem = new int[r][c];
for (int[] row : mem) Arrays.fill(row, -1);
int dfs(int x, int y) {
  if (mem[x][y] != -1) return mem[x][y];
  int best = 1;
  for (int[] d : dir) {
    int nx = x + d[0], ny = y + d[1];
    if (inRange(nx, ny) && height[nx][ny] < height[x][y])
      best = Math.max(best, dfs(nx, ny) + 1);
  }
  return mem[x][y] = best;
}

Greedy Strategies

Interval Problems

Maximum number of non-overlapping intervals:

Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int cnt = 0, lastEnd = Integer.MIN_VALUE;
for (int[] inv : intervals) {
  if (inv[0] > lastEnd) { cnt++; lastEnd = inv[1]; }
}

Minimum meeting rooms (interval partitioning):

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int[] inv : intervals) {
  if (!pq.isEmpty() && pq.peek() < inv[0]) pq.poll();
  pq.offer(inv[1]);
}

Minimum intervals to cover a range:

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int i = 0, ans = 0, curStart = targetStart;
while (i < n && curStart < targetEnd) {
  int maxRight = curStart;
  while (i < n && intervals[i][0] <= curStart) {
    maxRight = Math.max(maxRight, intervals[i][1]);
    i++;
  }
  if (maxRight == curStart) break; // cannot cover
  ans++; curStart = maxRight;
}

Huffman Coding

PriorityQueue<Long> pq = new PriorityQueue<>();
for (long v : arr) pq.offer(v);
long cost = 0;
while (pq.size() > 1) {
  long a = pq.poll(), b = pq.poll();
  cost += a + b;
  pq.offer(a + b);
}

Load Balancing (Acrobatic Cows)

Sort by weight + strength ascending:

Arrays.sort(cows, Comparator.comparingLong(c -> c[0] + c[1]));
long totalW = 0, maxRisk = Long.MIN_VALUE;
for (long[] c : cows) {
  maxRisk = Math.max(maxRisk, totalW - c[1]);
  totalW += c[0];
}

Warehouse Location (Absolute Value Inequality)

Arrays.sort(positions);
long median = positions[positions.length / 2];
long dist = 0;
for (long p : positions) dist += Math.abs(p - median);

Job Scheduling (Sorting Inequality)

Arrays.sort(processingTimes);
long totalWait = 0;
for (int i = 0; i < n; i++) totalWait += processingTimes[i] * (n - i - 1);