Data Structure1 Practice2 Interview

Adjacency Matrix

GuideCode Labs

Dense graph representation using a vertex-by-vertex matrix for constant-time edge lookup. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Adjacency Matrix when the prompt's constraints and required operations match this shape: Dense graph representation using a vertex-by-vertex matrix for constant-time edge lookup.

On this page · Mental Model

Checking your account…

Mental Model

An adjacency matrix assigns one cell to every ordered vertex pair. matrix[u][v] states whether or with what weight edge u → v exists, even when most cells are empty.

One Cell per Possible Edge

The matrix always uses O(V squared) space. Directed graphs need not be symmetric. In a simple undirected graph, matrix[u][v] == matrix[v][u]; diagonal cells represent self-loops rather than ordinary vertices.

Build a Symmetric Matrix

Allocate rows independently, then write both directions for each undirected edge. Duplicate edges overwrite the same cells harmlessly when the matrix stores booleans.

Build a Symmetric Edge Matrix

Reference

def build_adjacency_matrix(node_count, edges):
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        matrix[left][right] = 1
        matrix[right][left] = 1
    return matrix

Practice

Implement build_adjacency_matrix(node_count, edges). Return an independent-row 0/1 matrix for an undirected graph, including self-loops.

def build_adjacency_matrix(node_count, edges):
    matrix = [[0] * node_count] * node_count
    for left, right in edges:
        matrix[left][right] = 1
    return matrix

Public tests

Verify symmetry and row ownership

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Constant-Time Edge Queries

One edge query is O(1). Enumerating all neighbors still scans a complete row in O(V), and counting common neighbors compares two rows in O(V). This tradeoff favors dense graphs or query-heavy tasks.

Query Edges and Common Neighbors

Reference

def edge_query_summary(matrix, queries):
    result = []
    for left, right in queries:
        common = sum(a and b for a, b in zip(matrix[left], matrix[right]))
        result.append([bool(matrix[left][right]), common])
    return result

Practice

Implement edge_query_summary(matrix, queries). For each (u, v), return [has_edge, common_neighbor_count].

def edge_query_summary(matrix, queries):
    return [[False, 0] for _ in queries]

Public tests

Verify direct and common-neighbor queries

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Matrix or List

Choose a matrix when V is small, density is high, or arbitrary edge lookup dominates. Choose an adjacency list when the graph is sparse or algorithms repeatedly enumerate actual neighbors. For weighted graphs, choose a sentinel distinct from valid zero-weight edges.

Common Pitfalls

[[0] * V] * V aliases rows and mirrors unintended updates.
Writing one direction for an undirected edge breaks symmetry.
Treating a zero cell as absent fails when zero is a valid edge weight.
Claiming O(V + E) traversal while scanning V cells for every visited vertex is incorrect.

Explain It in an Interview

State what a cell and diagonal mean, then justify the O(V squared) memory purchase with density or query requirements. Separate constant edge lookup from linear neighbor enumeration.

Build Graph Representations(opens in a new tab) compares storage forms. Validate a Partial Sudoku(opens in a new tab) uses matrix-like coordinate constraints, though its relationships are implicit rather than edges.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Adjacency Matrix itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Core Adjacency Matrix workflow	`O(V^2 + E + V log V)`	`O(V^2 + E + V log V)`	Accumulate canonical neighbors in per-node sets while writing symmetric matrix cells, then sort each set for deterministic output.

Space

O(V^2 + E) for the demonstrated Adjacency Matrix workflow.

Assumptions

Exact bounds depend on copying, slicing, insertion position, and whether a new result is materialized.
The bound counts the operations in Build Graph Representations and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Adjacency Matrix invariant before coding and preserve it after every update, traversal step, or recursive return.
Represent sparse neighbor relationships and dense edge lookup from one graph contract. This remains true after every accepted operation.
Normalize undirected edges, duplicates, and self-loops consistently. This remains true after every accepted operation.

When To Use Or Avoid Adjacency Matrix

Use It When

Use Adjacency Matrix when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Adjacency Matrix invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def build_graph_representations(node_count, edges):
    pass

Use instead

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]

Where you will hit this: Build Graph Representations(opens in a new tab)

Breaking the central invariant

Records only the listed edge direction, producing a directed graph instead of the required undirected graph.

Prevent it: Keep this invariant visible while editing: State the precise Adjacency Matrix invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def build_graph_representations(node_count, edges):
    adjacency = [[] for _ in range(node_count)]
    matrix = [[0] * node_count for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].append(right)
        matrix[left][right] = 1
    return [adjacency, matrix]

Use instead

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]

Where you will hit this: Build Graph Representations(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(V^2 + E + V log V).

Avoid

def build_graph_representations(node_count, edges):
    adjacency = [[] for _ in range(node_count)]
    matrix = [[0] * node_count for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].append(right)
        matrix[left][right] = 1
    return [adjacency, matrix]

Use instead

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]

Where you will hit this: Validate a Partial Sudoku(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…