Articulation Points in Graph in DSA Typescript - Time & Space Complexity

Time Complexity: Articulation Points in Graph

O(n + m)

Understanding Time Complexity

We want to understand how the time needed to find articulation points changes as the graph grows.

Specifically, how does the algorithm's work increase with more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findArticulationPoints(graph: number[][]): number[] {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const parent = new Array(n).fill(-1);
  const ap = new Array(n).fill(false);
  let time = 0;

  function dfs(u: number) {
    visited[u] = true;
    disc[u] = low[u] = ++time;
    let children = 0;
    for (const v of graph[u]) {
      if (!visited[v]) {
        children++;
        parent[v] = u;
        dfs(v);
        low[u] = Math.min(low[u], low[v]);
        if (parent[u] === -1 && children > 1) ap[u] = true;
        if (parent[u] !== -1 && low[v] >= disc[u]) ap[u] = true;
      } else if (v !== parent[u]) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) dfs(i);
  }

  return ap.map((isAp, idx) => isAp ? idx : -1).filter(x => x !== -1);
}
    

This code finds all articulation points in a graph using depth-first search and tracking discovery and low times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Depth-first search (DFS) visits each node and explores its neighbors.
• How many times: Each node and edge is visited once during DFS traversal.

How Execution Grows With Input

As the graph grows, the algorithm visits every node and edge once.

Input Size (n nodes, m edges)	Approx. Operations
10 nodes, 15 edges	About 25 visits (nodes + edges)
100 nodes, 200 edges	About 300 visits
1000 nodes, 5000 edges	About 6000 visits

Pattern observation: The work grows roughly in proportion to the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the total number of nodes and edges in the graph.

Common Mistake

[X] Wrong: "The algorithm checks every pair of nodes, so it must be O(n²)."

[OK] Correct: The DFS only visits each edge and node once, not every pair, so it is more efficient than checking all pairs.

Interview Connect

Understanding this linear time complexity helps you explain how graph traversal algorithms efficiently find key points in networks.

Self-Check

"What if the graph was represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"