FastPrepMinimum Unreachable Warehouses

Minimum Unreachable Warehouses

Visa logoVisa● MediumINTERNOA
Learn

Problem statement

There are warehouseNodes warehouses numbered from 1 through warehouseNodes. The parallel arrays warehouseFrom and warehouseTo describe undirected roads: road i connects warehouseFrom[i] and warehouseTo[i].

You must choose one direction for every road. A warehouse is reachable when at least one directed road points into it; otherwise it is unreachable.

Return the minimum possible number of unreachable warehouses after directing every road. An isolated warehouse is a one-vertex tree component and therefore contributes one unreachable warehouse.

Function

minimumUnreachableWarehouses(warehouseNodes: int, warehouseFrom: int[], warehouseTo: int[]) → int

Examples

Example 1

warehouseNodes = 6warehouseFrom = [1,2,4,5,6]warehouseTo = [2,3,5,6,4]return = 1

Warehouses 1, 2, 3 form a tree, so every orientation leaves at least one warehouse without an incoming road. Warehouses 4, 5, 6 form a cycle, whose roads can be directed in a loop. Only the tree component contributes to the answer.

Example 2

warehouseNodes = 3warehouseFrom = [1,2,3]warehouseTo = [2,3,1]return = 0

All three warehouses lie on one cycle. Direct the roads as 1 -> 2, 2 -> 3, and 3 -> 1 so every warehouse has an incoming road.

Example 3

warehouseNodes = 5warehouseFrom = []warehouseTo = []return = 5

Every isolated warehouse is its own tree component, and every one has no incoming road.

Constraints

  • 1 <= warehouseNodes <= 2 * 10^5
  • 0 <= warehouseFrom.length = warehouseTo.length <= 2 * 10^5
  • 1 <= warehouseFrom[i], warehouseTo[i] <= warehouseNodes
  • Each array pair represents one undirected road.

More Visa problems

See Visa hiring insights
public int minimumUnreachableWarehouses(int warehouseNodes, int[] warehouseFrom, int[] warehouseTo) {
  // write your code here
}
warehouseNodes6
warehouseFrom[1,2,4,5,6]
warehouseTo[2,3,5,6,4]
expected1
Checking account…