Visa Application Processing Order

Problem Context

A tech company is helping its staff software engineers apply for work visas. Each engineer has a list of prerequisite visa documents that must be approved before their application can proceed. Your task is to determine the order in which visa applications should be processed, or report if it's impossible due to circular dependencies.

This is essentially a topological sort problem where engineers are nodes and document dependencies form directed edges.

Problem Description

You are given n engineers numbered from 0 to n-1. You are also given a list of prerequisites where prerequisites[i] = [a, b] means engineer a's visa application depends on engineer b's application being approved first.

Return a valid processing order of all n engineers. If no valid order exists (i.e., there is a circular dependency), return an empty array [].

Input Format

• n (integer): the number of engineers
• prerequisites (list of pairs): each pair [a, b] means engineer b must be processed before engineer a

Output Format

Return a list of integers representing a valid topological ordering of engineers 0 to n-1. If multiple valid orderings exist, return any one of them. If no valid ordering exists, return [].

Examples

Example 1

Input: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3] or [0, 2, 1, 3]
Explanation: Engineer 0 has no dependencies, so they go first. Engineers 1 and 2 both depend on 0, so they come next (in any order). Engineer 3 depends on both 1 and 2, so they go last.

Example 2

Input: n = 2, prerequisites = [[1,0]]
Output: [0, 1]
Explanation: Engineer 0 must be processed before engineer 1.

Example 3

Input: n = 2, prerequisites = [[0,1],[1,0]]
Output: []
Explanation: Engineer 0 depends on 1 and engineer 1 depends on 0. This circular dependency makes it impossible to determine a valid processing order.

Approach Hints

1. Build a graph: Represent dependencies as a directed adjacency list and track in-degrees (number of incoming edges) for each node.
2. Kahn's Algorithm (BFS-based topological sort):
   • Start with all nodes that have in-degree 0 (no prerequisites).
   • Process each node, reducing the in-degree of its neighbors.
   • Add neighbors with in-degree 0 to the queue.
3. Cycle Detection: If the result contains fewer than n nodes, a cycle exists — return [].
4. Alternative: DFS-based topological sort with a visited/recursion stack for cycle detection.

Time Complexity: O(V + E) where V = engineers, E = prerequisites.