FastPrep
Problem · Graph

Lexicographically Smallest Dependency Order

Learn this problem
● MediumOkta logoOktaFULLTIMEPHONE SCREEN

Problem statement

There are n tasks labeled from 0 to n - 1. Each pair [before, after] in dependencies means that before must be completed before after.

Return the lexicographically smallest order that completes every task. If the dependencies contain a cycle, return an empty array.

Function

dependencyOrder(n: int, dependencies: int[][]) → int[]

Examples

Example 1

n = 4dependencies = [[0,2],[1,2],[1,3]]return = [0,1,2,3]

Tasks 0 and 1 begin ready, so task 0 is chosen first; the remaining choices follow the same smallest-label rule.

Example 2

n = 3dependencies = [[0,1],[1,2],[2,0]]return = []

Every task belongs to a cycle, so no complete order exists.

Constraints

  • 1 <= n <= 100000
  • 0 <= dependencies.length <= 200000
  • Every dependency contains two distinct valid task labels.
  • No dependency pair is repeated.

More Okta problems

drafts saved locally
public int[] dependencyOrder(int n, int[][] dependencies) {
    // Write your code here.
}
n4
dependencies[[0,2],[1,2],[1,3]]
expected[0,1,2,3]
checking account