Topological Sort on grid

Question

Given a directed acyclic graph (DAG) represented as a grid, implement a function to perform a topological sort on the grid. The function should return a list of nodes in a linear order such that for every directed edge from node A to node B, node A comes before node B in the ordering. The input will be a 2D array representing the grid, and the output should be a list of nodes in topologically sorted order.

Codemia · Accepted Answer

The problem presents a directed acyclic graph (DAG) represented as a grid. Each cell in the grid can be viewed as a node in the graph, and the directed edges can be represented by the adjacency relationship between nodes. The topological sort is a linear ordering of vertices such that for every directed edge from vertex A to vertex B, A appears before B in the ordering. Given that this is a grid, we can treat each cell as a node and use the relationships between adjacent cells to define edges. A suitable approach for this is to use Depth-First Search (DFS) or Kahn's algorithm to perform the topological sort, as both are effective for processing DAGs.

1. **Building the Graph**: We will first construct the graph from the grid by iterating through each cell. For each cell, we will check its adjacent cells (right and down) to establish directed edges. For a cell at (i, j), if it points to (i, j+1) or (i+1, j), these become edges in our graph. 
2. **Indegree Calculation**: We will maintain an indegree array to count the number of incoming edges for each node, which helps in identifying nodes with no dependencies. 
3. **Topological Sorting using Kahn's Algorithm**: We will use a queue to process nodes with an indegree of 0. We will repeatedly dequeue a node, add it to the result list, and decrease the indegree of its neighbors. If a neighbor's indegree becomes zero, it will be added to the queue. 
4. **Result Verification**: If the result list contains fewer nodes than expected, this indicates a cycle, but since the input is guaranteed to be a DAG, we can assume all nodes will be processed properly.

Here is the Python solution implementing the above approach:

```python
from collections import deque

def topological_sort_grid(grid):
    if not grid or not grid[0]:
        return []

rows, cols = len(grid), len(grid[0])
    indegree = [[0] * cols for _ in range(rows)]
    graph = [[[] for _ in range(cols)] for _ in range(rows)]

# Build the graph and indegree count
    for i in range(rows):
        for j in range(cols):
            if j + 1 < cols:  # edge to right
                graph[i][j].append((i, j + 1))
                indegree[i][j + 1] += 1
            if i + 1 < rows:  # edge to down
                graph[i][j].append((i + 1, j))
                indegree[i + 1][j] += 1

# Kahn's algorithm for topological sort
    queue = deque()
    result = []

# Initialize the queue with nodes of indegree 0
    for i in range(rows):
        for j in range(cols):
            if indegree[i][j] == 0:
                queue.append((i, j))

while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node[0]][node[1]]:
            indegree[neighbor[0]][neighbor[1]] -= 1
            if indegree[neighbor[0]][neighbor[1]] == 0:
                queue.append(neighbor)

return result
```

The time complexity of this solution is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. In the case of a grid, V is equal to rows * cols (the number of cells), and E is at most 2 * V (each cell can point to two other cells). Thus, the overall time complexity remains linear with respect to the number of cells in the grid. The space complexity is also O(V + E), primarily for storing the graph and the indegree array.

1. **Empty Grid**: If the grid is empty (i.e., `grid = []`), the function should return an empty list. 
2. **Single Cell Grid**: If the grid contains only one cell (i.e., `grid = [[1]]`), the output should simply return that single node. 
3. **No Edges**: In a scenario where the grid is populated but there are no edges (isolated nodes), the output should still reflect all nodes in their original order since they have no dependencies. Example: `grid = [[1, 2], [3, 4]]` should return `[(0, 0), (0, 1), (1, 0), (1, 1)]`.

Topological Sort on grid

Square/Block

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Square/Block Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string