Bigbasket Item Preparation Sequence
In Bigbasket's fulfillment centers, efficiently preparing and stocking grocery items is critical. Some items have direct prerequisites, meaning one item must be fully prepared or stocked before another can begin. For instance, a base ingredient might need to be processed before it can be used in a final product, or a specific shelf must be stocked before items are placed on it. Ensuring these dependencies are met is crucial for smooth and timely operations.
Your task is to determine a valid sequence in which all grocery items can be prepared, respecting all given prerequisite relationships. If item A is a prerequisite for item B, then A must appear earlier than B in the preparation sequence. If it's impossible to prepare all items due to conflicting or circular dependencies, you should indicate this.
numItems: An integer representing the total number of distinct grocery items. These items are labeled from 0 to numItems - 1.prerequisites: An array of pairs, where each inner array [u, v] signifies that item u must be prepared before item v.numItems. If no such order exists (e.g., due to a circular dependency), return an empty array [].0 up to numItems - 1.numItems exactly once.Examples
Example 1
Input:
numItems = 2, prerequisites = [[1, 0]]
Output:
[1,0]
Note:
Item 1 must be prepared before Item 0. A valid sequence is [1, 0].
Example 2
Input:
numItems = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output:
[3,1,2,0]
Note:
Item 3 must be prepared before 1 and 2. Items 1 and 2 must be prepared before 0. A valid sequence is [3, 1, 2, 0]. [3, 2, 1, 0] would also be valid.
Example 3
Input:
numItems = 2, prerequisites = [[0, 1], [1, 0]]
Output:
[]
Note:
There is a circular dependency: Item 0 requires 1, and Item 1 requires 0. No valid preparation sequence can be formed.
Constraints
1 <= numItems <= 20000 <= prerequisites.length <= numItems * (numItems - 1) / 20 <= u, v < numItems for all [u, v] in prerequisitesu != v for all [u, v] in prerequisites (no item is a prerequisite for itself)[u, v] in prerequisites are unique.Loading editor...