Adjacency Matrix Representation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix after adding edges

What is the printed adjacency matrix after adding edges between nodes 0-1, 1-2, and 2-0 in an undirected graph of 3 nodes?

DSA Typescript

class Graph {
  matrix: number[][];
  size: number;
  constructor(size: number) {
    this.size = size;
    this.matrix = Array.from({ length: size }, () => Array(size).fill(0));
  }
  addEdge(u: number, v: number) {
    this.matrix[u][v] = 1;
    this.matrix[v][u] = 1;
  }
  printMatrix() {
    for (let i = 0; i < this.size; i++) {
      console.log(this.matrix[i].join(' '));
    }
  }
}

const g = new Graph(3);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.printMatrix();

A

0 0 0
0 0 0
0 0 0

B

0 1 0
1 0 1
0 1 0

C

1 1 1
1 1 1
1 1 1

D

0 1 1
1 0 1
1 1 0

💡 Hint

Think about how undirected edges are represented symmetrically in the matrix.

Each edge between nodes u and v sets matrix[u][v] and matrix[v][u] to 1. Since edges are between 0-1, 1-2, and 2-0, the matrix is symmetric with 1s at those positions.

❓ Predict Output

intermediate

Output after removing an edge in adjacency matrix

What is the adjacency matrix output after removing the edge between nodes 1 and 2 from the previous graph?

DSA Typescript

class Graph {
  matrix: number[][];
  size: number;
  constructor(size: number) {
    this.size = size;
    this.matrix = Array.from({ length: size }, () => Array(size).fill(0));
  }
  addEdge(u: number, v: number) {
    this.matrix[u][v] = 1;
    this.matrix[v][u] = 1;
  }
  removeEdge(u: number, v: number) {
    this.matrix[u][v] = 0;
    this.matrix[v][u] = 0;
  }
  printMatrix() {
    for (let i = 0; i < this.size; i++) {
      console.log(this.matrix[i].join(' '));
    }
  }
}

const g = new Graph(3);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.removeEdge(1, 2);
g.printMatrix();

A

0 0 0
0 0 0
0 0 0

B

0 1 1
1 0 1
1 1 0

C

0 1 1
1 0 0
1 0 0

D

1 1 1
1 1 1
1 1 1

💡 Hint

Removing an edge sets the corresponding matrix entries to zero.

Removing edge 1-2 sets matrix[1][2] and matrix[2][1] to 0, while other edges remain.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this code produce when creating an adjacency matrix for 3 nodes?

DSA Typescript

class Graph {
  matrix: number[][];
  size: number;
  constructor(size: number) {
    this.size = size;
    this.matrix = Array(size).fill(Array(size).fill(0));
  }
}

const g = new Graph(3);
g.matrix[0][1] = 1;
console.log(g.matrix);

A All rows change when one element is updated because inner arrays are shared

B TypeError because matrix is undefined

C SyntaxError due to missing semicolon

D No error, matrix updates correctly

💡 Hint

Check how Array.fill works with objects inside.

Using Array.fill with an array fills all positions with the same reference, so changing one row changes all rows.

❓ Predict Output

advanced

Output of adjacency matrix for directed graph

What is the adjacency matrix output after adding directed edges 0->1, 1->2, and 2->0 in a graph of 3 nodes?

DSA Typescript

class DirectedGraph {
  matrix: number[][];
  size: number;
  constructor(size: number) {
    this.size = size;
    this.matrix = Array.from({ length: size }, () => Array(size).fill(0));
  }
  addEdge(u: number, v: number) {
    this.matrix[u][v] = 1;
  }
  printMatrix() {
    for (let i = 0; i < this.size; i++) {
      console.log(this.matrix[i].join(' '));
    }
  }
}

const g = new DirectedGraph(3);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.printMatrix();

A

0 1 0
0 0 1
1 0 0

B

0 1 1
1 0 1
1 1 0

C

0 0 0
0 0 0
0 0 0

D

1 0 0
0 1 0
0 0 1

💡 Hint

Directed edges only set one direction in the matrix.

Each directed edge sets matrix[u][v] to 1 only, so the matrix is not symmetric.

🧠 Conceptual

expert

Memory complexity of adjacency matrix vs adjacency list

Which statement correctly compares the memory usage of adjacency matrix and adjacency list for a graph with V vertices and E edges?

A Both adjacency matrix and adjacency list use O(V^2) memory

B Adjacency matrix uses O(V^2) memory regardless of edges; adjacency list uses O(V + E) memory

C Adjacency matrix uses O(E) memory; adjacency list uses O(V) memory

D Adjacency matrix uses O(V + E) memory; adjacency list uses O(V^2) memory

💡 Hint

Think about how adjacency matrix stores all possible edges.

Adjacency matrix always stores V x V entries, so O(V^2). Adjacency list stores only existing edges plus vertices, so O(V + E).

Practice

1. What does an adjacency matrix represent in a graph?
Adjacency matrix is a way to show connections between nodes. What does a 1 in the matrix mean?

easy

A. There is no edge between two nodes

B. The graph is weighted

C. The nodes are the same

D. There is a direct edge between two nodes

Solution

1. Step 1: Understand adjacency matrix basics

   An adjacency matrix uses rows and columns to represent nodes. Each cell shows if two nodes connect.

2. Step 2: Interpret the value 1 in the matrix

   A value of 1 means there is a direct edge between the nodes represented by that row and column.

3. Final Answer:

   There is a direct edge between two nodes -> Option D

4. Quick Check:

   1 means edge exists [OK]

Hint: 1 means connected, 0 means no connection [OK]

Common Mistakes:

• Thinking 1 means no edge
• Confusing node identity with connection
• Assuming matrix shows weights always

2. Which of the following is the correct TypeScript syntax to declare a 3x3 adjacency matrix initialized with zeros without shared row references?

easy

A. const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]];

B. const matrix: number[3][3] = new Array(3).fill(new Array(3).fill(0));

C. const matrix = Array(3).map(Array(3).fill(0));

D. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0));

Solution

1. Step 1: Check TypeScript array declaration syntax

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; uses explicit 2D array with nested arrays and zeros, which is valid syntax and creates independent rows.

2. Step 2: Identify issues in other options

   const matrix: number[3][3] = new Array(3).fill(new Array(3).fill(0)); uses invalid TypeScript syntax for fixed-size arrays. const matrix = Array(3).map(Array(3).fill(0)); passes an array to map() instead of a function, causing a runtime error. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0)); uses fill with the same inner array reference, causing shared rows.

3. Final Answer:

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; -> Option A

4. Quick Check:

   Explicit nested arrays with zeros [OK]

Hint: Use explicit nested arrays to avoid shared references [OK]

Common Mistakes:

• Using fill with same inner array causing shared rows
• Passing non-function to map()
• Wrong type annotations

3. Given the following adjacency matrix for a directed graph:

const matrix = [
  [0, 1, 0],
  [0, 0, 1],
  [1, 0, 0]
];
console.log(matrix[2][0]);

What will be the output?

medium

A. 1

B. Error

C. undefined

D. 0

Solution

1. Step 1: Locate matrix[2][0]

   Row 2 is [1, 0, 0], so element at index 0 is 1.

2. Step 2: Confirm output of console.log

   console.log prints the value 1 found at matrix[2][0].

3. Final Answer:

   1 -> Option A

4. Quick Check:

   matrix[2][0] = 1 [OK]

Hint: Remember matrix[row][column] indexing [OK]

Common Mistakes:

• Confusing row and column indices
• Expecting zero instead of one
• Thinking index out of range

4. Consider this TypeScript code snippet to create an adjacency matrix for 3 nodes:

const size = 3;
const matrix = new Array(size).fill(new Array(size).fill(0));
matrix[0][1] = 1;
console.log(matrix);

What is the problem with this code?

medium

A. It creates a matrix with all zeros correctly

B. The matrix is not initialized at all

C. All rows point to the same inner array, so all rows change when one changes

D. It throws a runtime error

Solution

1. Step 1: Understand fill with reference types

   Using fill with new Array(size).fill(0) creates one inner array shared by all rows.

2. Step 2: Effect of modifying matrix[0][1]

   Changing matrix[0][1] changes the shared inner array, so all rows show the change.

3. Final Answer:

   All rows point to the same inner array, so all rows change when one changes -> Option C

4. Quick Check:

   Shared inner array causes unexpected updates [OK]

Hint: Avoid fill with objects/arrays; use map for unique rows [OK]

Common Mistakes:

• Assuming fill creates independent arrays
• Ignoring shared reference behavior
• Expecting only one row to change

5. You have an undirected graph with 4 nodes. You want to represent it using an adjacency matrix in TypeScript. Which of the following code snippets correctly initializes the matrix and sets an edge between node 1 and node 3?

hard

A. const size = 4;
const matrix = new Array(size).fill(new Array(size).fill(0));
matrix[1][3] = 1;
matrix[3][1] = 1;

B. const size = 4;
const matrix = Array.from({ length: size }, () => Array(size).fill(0));
matrix[1][3] = 1;
matrix[3][1] = 1;

C. const size = 4;
const matrix = Array(size).fill(Array(size).fill(0));
matrix[1][3] = 1;

D. const size = 4;
const matrix = Array(size).map(() => Array(size).fill(0));
matrix[1][3] = 1;

Solution

1. Step 1: Check matrix initialization for unique rows

   const size = 4; const matrix = Array.from({ length: size }, () => Array(size).fill(0)); matrix[1][3] = 1; matrix[3][1] = 1; uses Array.from with a function to create unique inner arrays, avoiding shared references.

2. Step 2: Verify setting edges for undirected graph

   Setting matrix[1][3] and matrix[3][1] to 1 correctly represents an undirected edge.

3. Step 3: Identify issues in other options

   Options B and C use fill causing shared inner arrays. const size = 4; const matrix = Array(size).map(() => Array(size).fill(0)); matrix[1][3] = 1; initializes correctly but only sets matrix[1][3] = 1, missing matrix[3][1] = 1 for undirected graph.

4. Final Answer:

   const size = 4; const matrix = Array.from({ length: size }, () => Array(size).fill(0)); matrix[1][3] = 1; matrix[3][1] = 1; -> Option B

5. Quick Check:

   Use Array.from with function for unique rows [OK]

Hint: Use Array.from with function to avoid shared rows [OK]

Common Mistakes:

• Using fill causing shared inner arrays
• Using map on empty array without initialization
• Setting only one direction for undirected edge