FastPrepFind Trapped Zones
Problems/Find Trapped Zones

Find Trapped Zones

ServiceNow logoServiceNow● HardFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a first-round ServiceNow IC2 interview, the candidate got cities linked by one-way roads. The first part asked for every group of cities that can all reach one another, and the follow-up asked which of those groups can be entered from outside but never left.

The post gives one example and no limits, and it lets the cities inside a group come in any order. Here only the follow-up answer is judged, each group is sorted and the groups are ordered by their smallest city, and there are at most 2000 cities and 4000 distinct roads with no road from a city to itself.

The judged task matches the post at about 90%.

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 <= 2000
  • 0 <= connections.length <= 4000
  • connections[i].length == 2
  • 0 <= a, b <= n - 1
  • a != b
  • No road appears more than once in connections.

More ServiceNow interview questions

  • LRU CachePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Maximum Subarray Sum with One DeletionPHONE SCREEN · Seen Nov 2026
  • Subarray Sum Equals KONSITE INTERVIEW · Seen Nov 2026
  • Find Max Minimum Value Using K Elements 🐴OA · Seen Mar 2024
  • Maximum Sum of Balanced SubsequenceOA · Seen Mar 2024

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
All ServiceNow interview questionsSee ServiceNow hiring insights
Saved
class Solution {
    public List<List<Integer>> findTrappedZones(int n, int[][] connections) {
        // Write your code here.
    }
}
Checking account…