Find Deadlocked Transactions

Your on-call dashboard samples the database's lock table (like Postgres pg_locks + pg_blocking_pids) and builds wait-for edges: [waiter, holder] means transaction waiter is blocked by a lock held by holder.

Implement findDeadlocked(waits) that returns every transaction that is part of at least one cycle — those can never make progress without the database aborting one of them. Return the names sorted ascending; return an empty list when there is no deadlock. Transactions that merely wait on a cycle (but are not in it) are not deadlocked.

Example 1

Input: waits = [["T1","T2"],["T2","T1"],["T3","T1"]]
Output: ["T1","T2"]
Explanation: T1 and T2 wait for each other. T3 is blocked, but not part of the cycle.

Example 2

Input: waits = [["A","B"],["B","C"]]
Output: []
Explanation: A chain of waits with no cycle resolves when C commits.

Constraints

0 ≤ waits.length ≤ 1,000
Names are non-empty strings
A transaction may wait on several others

Solution and explanation

Show the solution

Time O(V · (V + E)) · Space O(V + E)

Treat the edges as a directed graph. A transaction is deadlocked exactly when it lies on a cycle, i.e. it can reach itself. The reference solutions run a DFS from each waiter (O(V·(V+E)), fine for a lock table snapshot); a production monitor would use strongly connected components to find all cycles in one pass.

This is the same check databases perform: Postgres runs it when a lock wait exceeds deadlock_timeout, InnoDB on every wait. See How Deadlocks Happen.

Reference solution

function findDeadlocked(waits) {
  const graph = new Map();
  for (const [waiter, holder] of waits) {
    if (!graph.has(waiter)) graph.set(waiter, []);
    graph.get(waiter).push(holder);
  }
  const reachesItself = (start) => {
    const seen = new Set();
    const stack = [...graph.get(start)];
    while (stack.length) {
      const node = stack.pop();
      if (node === start) return true;
      if (seen.has(node)) continue;
      seen.add(node);
      stack.push(...(graph.get(node) ?? []));
    }
    return false;
  };
  return [...graph.keys()].filter(reachesItself).sort();
}

function findDeadlocked(waits: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [waiter, holder] of waits) {
    if (!graph.has(waiter)) graph.set(waiter, []);
    graph.get(waiter)!.push(holder);
  }
  const reachesItself = (start: string): boolean => {
    const seen = new Set<string>();
    const stack = [...graph.get(start)!];
    while (stack.length) {
      const node = stack.pop()!;
      if (node === start) return true;
      if (seen.has(node)) continue;
      seen.add(node);
      stack.push(...(graph.get(node) ?? []));
    }
    return false;
  };
  return [...graph.keys()].filter(reachesItself).sort();
}

def find_deadlocked(waits: list[list[str]]) -> list[str]:
    graph: dict[str, list[str]] = {}
    for waiter, holder in waits:
        graph.setdefault(waiter, []).append(holder)

    def reaches_itself(start: str) -> bool:
        seen: set[str] = set()
        stack = list(graph[start])
        while stack:
            node = stack.pop()
            if node == start:
                return True
            if node in seen:
                continue
            seen.add(node)
            stack.extend(graph.get(node, []))
        return False

    return sorted(t for t in graph if reaches_itself(t))

<?php

function findDeadlocked(array $waits): array
{
    $graph = [];
    foreach ($waits as [$waiter, $holder]) {
        $graph[$waiter][] = $holder;
    }
    $result = [];
    foreach (array_keys($graph) as $start) {
        $start = (string) $start;
        $seen = [];
        $stack = $graph[$start];
        while ($stack) {
            $node = array_pop($stack);
            if ($node === $start) {
                $result[] = $start;
                break;
            }
            if (isset($seen[$node])) {
                continue;
            }
            $seen[$node] = true;
            foreach ($graph[$node] ?? [] as $next) {
                $stack[] = $next;
            }
        }
    }
    sort($result);
    return $result;
}

class Solution {
    public String[] findDeadlocked(String[][] waits) {
        Map<String, List<String>> graph = new LinkedHashMap<>();
        for (String[] edge : waits) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        }
        List<String> result = new ArrayList<>();
        for (String start : graph.keySet()) {
            Set<String> seen = new HashSet<>();
            Deque<String> stack = new ArrayDeque<>(graph.get(start));
            while (!stack.isEmpty()) {
                String node = stack.pop();
                if (node.equals(start)) { result.add(start); break; }
                if (!seen.add(node)) continue;
                for (String next : graph.getOrDefault(node, List.of())) stack.push(next);
            }
        }
        Collections.sort(result);
        return result.toArray(new String[0]);
    }
}

Common mistakes

Reporting every blocked transaction instead of only those on a cycle.
Infinite loops when DFS doesn't track visited nodes.
Forgetting to sort the result.

Follow-up questions

Pick a victim to abort (e.g. the youngest transaction).
Find all cycles in O(V + E) with Tarjan's algorithm.

Example 1

Example 2

Constraints

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

Example 1

Example 2

Constraints

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

More Graphs problems