Build a Matrix With Conditions

▶

Steps

setup

Initialize Row Graph and In-Degree

Create adjacency list and in-degree array for row conditions. For each condition [u,v], add edge u->v and increment in-degree of v.

💡 Building the graph and in-degree array sets up the dependency structure needed for topological sorting.

Line:

graph = [[] for _ in range(n + 1)]
in_degree = [0] * (n + 1)
for u, v in conditions:
    graph[u].append(v)
    in_degree[v] += 1

💡 The graph and in-degree arrays represent all row dependencies explicitly.

setup

Initialize Row Queue with Zero In-Degree Nodes

Add all nodes with zero in-degree to the queue. These nodes have no dependencies and can be assigned positions first.

💡 Starting with zero in-degree nodes is essential for Kahn's algorithm to begin topological sorting.

Line:

queue = deque()
for i in range(1, n + 1):
    if in_degree[i] == 0:
        queue.append(i)

💡 Node 1 has zero in-degree, so it is the first candidate for position assignment.

traverse

Assign Position to Node 1 in Row Order

Dequeue node 1 from the queue and assign it position 0 in the row order. Mark node 1 as done.

💡 Assigning positions as nodes are dequeued establishes the topological order.

Line:

node = queue.popleft()
pos[node] = idx
idx += 1

💡 Node 1 is the first in the row order because it has no dependencies.

traverse

Update In-Degree of Node 2 and Enqueue if Zero

Decrease in-degree of node 2 by 1 due to processing node 1. Since in-degree of node 2 becomes zero, enqueue node 2.

💡 Reducing in-degree reflects that one dependency is resolved, enabling node 2 to be processed next.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1
    if in_degree[nei] == 0:
        queue.append(nei)

💡 Node 2 is now ready to be assigned a position after node 1.

traverse

Assign Position to Node 2 in Row Order

Dequeue node 2 and assign it position 1 in the row order. Mark node 2 as done.

💡 Assigning position to node 2 continues the topological order sequence.

Line:

node = queue.popleft()
pos[node] = idx
idx += 1

💡 Node 2 comes after node 1 in the row order.

traverse

Update In-Degree of Node 3 and Enqueue if Zero

Decrease in-degree of node 3 by 1 due to processing node 2. Since in-degree of node 3 becomes zero, enqueue node 3.

💡 Resolving dependencies step-by-step enables the next node to be processed in order.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1
    if in_degree[nei] == 0:
        queue.append(nei)

💡 Node 3 is now ready to be assigned a position after node 2.

traverse

Assign Position to Node 3 in Row Order

Dequeue node 3 and assign it position 2 in the row order. Mark node 3 as done.

💡 Completing the row order assignment finalizes the topological sort for rows.

Line:

node = queue.popleft()
pos[node] = idx
idx += 1

💡 Node 3 is last in the row order, completing the sequence 1->2->3.

setup

Initialize Column Graph and In-Degree

Create adjacency list and in-degree array for column conditions. For each condition [u,v], add edge u->v and increment in-degree of v.

💡 Building the column graph sets up dependencies for column positions, similar to rows.

Line:

graph = [[] for _ in range(n + 1)]
in_degree = [0] * (n + 1)
for u, v in conditions:
    graph[u].append(v)
    in_degree[v] += 1

💡 Column dependencies are represented explicitly for topological sorting.

setup

Initialize Column Queue with Zero In-Degree Nodes

Add all nodes with zero in-degree to the queue for column graph. These nodes have no dependencies and can be assigned positions first.

💡 Starting with zero in-degree nodes is essential for Kahn's algorithm to begin topological sorting for columns.

Line:

queue = deque()
for i in range(1, n + 1):
    if in_degree[i] == 0:
        queue.append(i)

💡 Node 3 has zero in-degree in column graph, so it is the first candidate for position assignment.

traverse

Assign Position to Node 3 in Column Order

Dequeue node 3 and assign it position 0 in the column order. Mark node 3 as done.

💡 Assigning positions as nodes are dequeued establishes the topological order for columns.

Line:

node = queue.popleft()
pos[node] = idx
idx += 1

💡 Node 3 is the first in the column order because it has no dependencies.

traverse

Update In-Degree of Node 2 and Enqueue if Zero (Column)

Decrease in-degree of node 2 by 1 due to processing node 3. Since in-degree of node 2 becomes zero, enqueue node 2.

💡 Resolving dependencies step-by-step enables the next node to be processed in column order.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1
    if in_degree[nei] == 0:
        queue.append(nei)

💡 Node 2 is now ready to be assigned a position after node 3 in column order.

traverse

Assign Position to Node 2 in Column Order

Dequeue node 2 and assign it position 1 in the column order. Mark node 2 as done.

💡 Assigning position to node 2 continues the topological order sequence for columns.

Line:

node = queue.popleft()
pos[node] = idx
idx += 1

💡 Node 2 comes after node 3 in the column order.

traverse

Update In-Degree of Node 1 and Enqueue if Zero (Column)

Decrease in-degree of node 1 by 1 due to processing node 2. Since in-degree of node 1 becomes zero, enqueue node 1.

💡 Resolving dependencies step-by-step enables the last node to be processed in column order.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1
    if in_degree[nei] == 0:
        queue.append(nei)

💡 Node 1 is now ready to be assigned a position after node 2 in column order.

traverse

Assign Position to Node 1 in Column Order

Dequeue node 1 and assign it position 2 in the column order. Mark node 1 as done.

💡 Completing the column order assignment finalizes the topological sort for columns.

Line:

node = queue.popleft()
pos[node] = idx
idx += 1

💡 Node 1 is last in the column order, completing the sequence 3->2->1.

insert

Construct Matrix Using Assigned Positions

Create an n x n matrix filled with zeros. For each number from 1 to n, place it at the row and column positions assigned by the topological sorts.

💡 Mapping numbers to their assigned positions builds the final matrix satisfying all conditions.

Line:

matrix = [[0] * n for _ in range(n)]
for num in range(1, n + 1):
    matrix[row_pos[num]][col_pos[num]] = num

💡 Positions from topological sorts directly translate to matrix coordinates.

reconstruct

Final Matrix Output

Return the constructed matrix where each number is placed according to the computed row and column positions.

💡 The final matrix satisfies all row and column conditions, completing the problem.

Line:

return matrix

💡 The matrix [[3,0,0],[0,2,0],[0,0,1]] reflects the orders 1->2->3 in rows and 3->2->1 in columns.

from collections import deque

def topological_sort_positions(conditions, n):
    graph = [[] for _ in range(n + 1)]  # STEP 1
    in_degree = [0] * (n + 1)          # STEP 1
    for u, v in conditions:             # STEP 1
        graph[u].append(v)              # STEP 1
        in_degree[v] += 1              # STEP 1
    queue = deque()                    # STEP 2
    for i in range(1, n + 1):          # STEP 2
        if in_degree[i] == 0:          # STEP 2
            queue.append(i)            # STEP 2
    pos = [0] * (n + 1)                # STEP 3
    idx = 0                           # STEP 3
    while queue:                      # STEP 3
        if len(queue) > 1:            # STEP 3
            pass  # multiple valid orders allowed
        node = queue.popleft()        # STEP 3
        pos[node] = idx               # STEP 3
        idx += 1                     # STEP 3
        for nei in graph[node]:       # STEP 4
            in_degree[nei] -= 1      # STEP 4
            if in_degree[nei] == 0:  # STEP 4
                queue.append(nei)    # STEP 4
    if idx != n:                     # STEP 5
        return []                   # STEP 5
    return pos                      # STEP 5

def buildMatrix(n, rowConditions, colConditions):
    row_pos = topological_sort_positions(rowConditions, n)  # STEP 6
    if not row_pos:                                         # STEP 6
        return []                                          # STEP 6
    col_pos = topological_sort_positions(colConditions, n)  # STEP 7
    if not col_pos:                                         # STEP 7
        return []                                          # STEP 7
    matrix = [[0] * n for _ in range(n)]                   # STEP 8
    for num in range(1, n + 1):                            # STEP 8
        matrix[row_pos[num]][col_pos[num]] = num          # STEP 8
    return matrix                                         # STEP 9

if __name__ == '__main__':
    n = 3
    rowConditions = [[1,2],[2,3]]
    colConditions = [[2,1],[3,2]]
    result = buildMatrix(n, rowConditions, colConditions)
    for row in result:
        print(row)

📊

Build a Matrix With Conditions - Watch the Algorithm Execute, Step by Step

Watching each step of the topological sort and matrix construction reveals how dependencies translate into positions, making the abstract concept concrete and intuitive.

Visiting: none

1

2

3

Visiting: none

1

2

3

Queue / Stack

1

Visiting: 1

1

2

3

Visiting: 1

Edge: 1 → 2

1

2

3

Queue / Stack

2

Visiting: 2

1

2

3

Visiting: 2

Edge: 2 → 3

1

2

3

Queue / Stack

3

Visiting: 3

1

2

3

Visiting: none

1

2

3

Visiting: none

1

2

3

Queue / Stack

3

Visiting: 3

1

2

3

Visiting: 3

Edge: 3 → 2

1

2

3

Queue / Stack

2

Visiting: 2

1

2

3

Visiting: 2

Edge: 2 → 1

1

2

3

Queue / Stack

1

Visiting: 1

1

2

3

Visiting: none

1

2

3

Visiting: none

1

2

3

Key Takeaways

✓ Topological sorting assigns positions respecting all dependency constraints.

Seeing nodes move from queue to done with position assignment clarifies how order is established beyond code.

✓ Separate topological sorts for rows and columns handle independent constraints elegantly.

Visualizing two graphs and their sorts side-by-side reveals how row and column orders combine to position elements.

✓ Cycle detection via incomplete processing ensures invalid inputs return empty results.

Watching the queue empty prematurely or nodes unprocessed highlights when no valid order exists.

Practice

1. Given the following Python code snippet implementing the optimal alien dictionary solution, what is the final returned order for the input words = ["wrt", "wrf", "er", "ett", "rftt"]?

from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nei in graph[c]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) < len(in_degree):
        return ""
    return "".join(order)

print(alienOrder(words))

easy

A. "wretf"

B. "wertf"

C. "wert"

D. "wrtef"

Solution

1. Step 1: Build graph and in-degree map

   Edges: w->e, e->r, r->t, t->f. In-degree counts: w=0, e=1, r=1, t=1, f=1.

2. Step 2: Perform BFS topological sort

   Start with 'w' (in-degree 0), then 'e', 'r', 't', 'f' in order as their in-degree drops to zero.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order "wertf" respects all precedence edges [OK]

Hint: Trace BFS queue and in-degree updates [OK]

Common Mistakes:

• Stopping early and missing characters
• Misordering characters with same in-degree
• Ignoring prefix invalid case

2. What is the time complexity of Kahn's Algorithm for finding a topological order in a graph with V vertices and E edges?

medium

A. O(V * E) because each vertex processes all edges repeatedly.

B. O(V^2) because in-degree updates require scanning all vertices.

C. O(V + E) because each vertex and edge is processed exactly once.

D. O(E log V) due to priority queue operations for ordering.

Solution

1. Step 1: Identify operations on vertices and edges

   Each vertex is enqueued and dequeued once; each edge is visited once to decrement in-degree.

2. Step 2: Sum total work

   Processing all vertices and edges once leads to O(V + E) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time in graph size is standard for BFS topological sort [OK]

Hint: Each edge and vertex processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing in-degree updates as scanning all vertices
• Thinking priority queues are used by default

3. What is the time complexity of the optimal leaf trimming algorithm for finding Minimum Height Trees in a tree with n nodes and n-1 edges?

medium

A. O(n²) because each leaf removal requires scanning all nodes.

B. O(n) because each edge and node is processed at most once during trimming.

C. O(n log n) due to priority queue operations for leaf selection.

D. O(n + m) where m is the number of edges, which equals n-1 here.

Solution

1. Step 1: Analyze leaf trimming operations

   Each node is added and removed from the leaves queue at most once. Each edge is visited when decrementing degrees.

2. Step 2: Combine node and edge processing

   Since the graph is a tree, edges = n-1. Total operations proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity matches leaf trimming algorithm [OK]

Hint: Each node and edge processed once [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing with BFS from each node
• Thinking priority queue is used

4. Suppose the course prerequisites can form multiple disconnected subgraphs and some courses have no prerequisites. How should Kahn's Algorithm be modified to return a valid order including all courses?

hard

A. Initialize the queue with all nodes having zero in-degree, including those in disconnected components.

B. Use backtracking to try all permutations since BFS cannot handle disconnected graphs.

C. Run DFS from each node separately and concatenate results without cycle checks.

D. Start BFS from any arbitrary node and ignore disconnected components.

Solution

1. Step 1: Identify disconnected components

   Courses with no prerequisites form disconnected subgraphs with zero in-degree nodes.

2. Step 2: Initialize queue with all zero in-degree nodes

   Queue must include all such nodes to process all components and produce a full valid order.

3. Step 3: Process BFS as usual

   Processing all zero in-degree nodes ensures all courses are included in the order.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Queue initialization with all zero in-degree nodes covers disconnected graphs [OK]

Hint: Queue must start with all zero in-degree nodes, not just one [OK]

Common Mistakes:

• Starting BFS from a single node only
• Ignoring disconnected components
• Skipping cycle detection in DFS

5. Suppose the problem is modified so that elements in the sequences can be reused multiple times (i.e., sequences may contain repeated elements). Which of the following changes to the DFS postorder topological sort approach is necessary to correctly determine if the original sequence can be uniquely reconstructed?

hard

A. No changes needed; the existing DFS approach handles repeated elements naturally.

B. Modify graph construction to allow multiple edges between the same nodes and adjust cycle detection accordingly.

C. Switch to BFS topological sort with a queue that tracks in-degree counts considering repeated edges.

D. Preprocess sequences to remove duplicates before building the graph, then run the original DFS approach.

Solution

1. Step 1: Understand impact of repeated elements

   Repeated elements mean multiple edges between same nodes may exist, affecting graph structure and cycle detection.

2. Step 2: Adjust graph and DFS accordingly

   Graph must allow multiple edges or count edge multiplicity; cycle detection must consider these to avoid false negatives or infinite recursion.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Handling repeated edges is essential for correctness with reused elements [OK]

Hint: Repeated elements require multi-edge aware graph and cycle detection [OK]

Common Mistakes:

• Assuming no changes needed
• Removing duplicates loses info
• Switching to BFS without handling repeats