Graphs/Find the City With the Smallest Number of NeighborsMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Find the City With the Smallest Number of Neighbors

Graphs·Medium

There are n cities numbered 0 to n - 1. You are given an array edges where edges[i] = [from, to, weight] represents a bidirectional weighted edge. Given an integer distanceThreshold, find the city with the smallest number of cities reachable with a distance of at most distanceThreshold. If there is a tie, return the city with the greatest number (largest index).

Use Floyd-Warshall to compute all-pairs shortest paths. Then, for each city, count how many other cities are reachable within the threshold.

Examples

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4

Output: 3

City 0 and city 3 each have 2 reachable cities within distance 4. Return 3 (largest index on tie).

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2

Output: 0

Constraints

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= from < to < n
1 <= weight <= 10^4
All pairs (from, to) are distinct.
1 <= distanceThreshold <= 10^4

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Graphs
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.