Find Trapped Zones
Updated
Problem statement
There are n cities, numbered from 0 to n - 1. Each entry connections[i] = [a, b] is a one-way road from city a to city b. A road from a to b does not let you travel from b back to a.
A zone is a largest possible group of cities in which every city can reach every other city of the group by following roads. Every city belongs to exactly one zone; a city that cannot reach any other city and come back forms a zone on its own.
A zone is trapped when both of these are true:
- at least one road enters it from a city in a different zone, and
- no road leaves it to a city in a different zone.
Once you enter a trapped zone, you can move between all of its cities, but you can never leave it.
Return every trapped zone. List the cities of each zone in increasing order, and order the zones by their smallest city. If no zone is trapped, return an empty list.
Function
findTrappedZones(n: int, connections: int[][]) → List<List<Integer>>Examples
Example 1
n = 8connections = [[0,1],[1,2],[2,3],[3,0],[3,4],[4,5],[5,4],[6,5],[6,7]]return = [[4,5],[7]]The zones are [0, 1, 2, 3] (a loop), [4, 5] (two roads in opposite directions), [6] and [7]. Zone [4, 5] is entered from cities 3 and 6 and has no road out, so it is trapped. Zone [7] is entered from city 6 and has no road out, so it is trapped. Zone [0, 1, 2, 3] has a road out (to 4), and zone [6] has roads out and no road in, so neither is trapped.
Example 2
n = 3connections = [[0,1],[1,2],[2,0]]return = []All three cities form one loop, so there is only one zone, [0, 1, 2]. No road enters it from another zone, so it is not trapped and the answer is empty.
Example 3
n = 4connections = [[0,1],[2,1],[1,3]]return = [[3]]No two cities can reach each other, so every city is its own zone. City 3 is entered from 1 and has no road out, so [3] is trapped. City 1 has a road out, and cities 0 and 2 have no road in.
Constraints
1 <= n <= 20000 <= connections.length <= 4000connections[i].length == 20 <= a, b <= n - 1a != b- No road appears more than once in
connections.
More ServiceNow interview questions
Similar questions at other companies
- Minimum Boards to Cover Roof HolesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Visit Desired Attractions Without Reusing a TrailDuolingo · PHONE SCREENDuolingo interview questions
- Attraction Route Without Reusing TrailsWhatNot · PHONE SCREENWhatNot interview questions
- Spreadsheet With Dependent CellsCharacter.AI · PHONE SCREEN
- Course Order and CycleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Evaluate Live Spreadsheet ExpressionsStrala · PHONE SCREEN
- Enumerate Directed Paths and CyclesByteDance · PHONE SCREENByteDance interview questions
- Process Graph Rule ValidationHadrian · PHONE SCREENHadrian interview questions
- Spreadsheet Formula EvaluatorPika · PHONE SCREEN
- Group Training Overdue RollupVanta · PHONE SCREEN