#1334

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find the City With the Smallest Number of Neighbors at a Threshold Distance

Find the city with the fewest neighbors within a given threshold distance using dynamic programming.

Problem Statement

You are given a graph where cities are represented as nodes, and roads between cities as weighted edges. Each city is numbered from 0 to n-1. You need to find the city with the fewest reachable neighbors within a given distance threshold. For each city, the distance to its neighboring cities is computed using the weights on the edges, and any city reachable within the threshold is counted as a neighbor.

Return the city with the smallest number of neighbors reachable within the threshold distance. If multiple cities have the same number of neighbors, return the city with the largest number. The distance between cities is the sum of edge weights along the shortest path.

Examples

Example 1

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

Output: 3

The figure above describes the graph. The neighboring cities at a distanceThreshold = 4 for each city are: City 0 -> [City 1, City 2] City 1 -> [City 0, City 2, City 3] City 2 -> [City 0, City 1, City 3] City 3 -> [City 1, City 2] Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2

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

The figure above describes the graph. The neighboring cities at a distanceThreshold = 2 for each city are: City 0 -> [City 1] City 1 -> [City 0, City 4] City 2 -> [City 3, City 4] City 3 -> [City 2, City 4] City 4 -> [City 1, City 2, City 3] The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints

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

Solution Approach

Use Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is ideal for this problem as it computes the shortest paths between all pairs of cities. By using it, you can find the number of reachable cities for each city within the threshold distance.

Dijkstra’s Algorithm from Each City

Alternatively, applying Dijkstra’s algorithm from every city can provide the shortest path distances to all other cities. This allows you to check the number of reachable neighbors at each distance threshold.

Identify the City with Fewest Neighbors

Once the shortest paths are computed, count the number of cities that are reachable within the threshold distance for each city. Return the city with the smallest number of neighbors, or the city with the greatest number if there’s a tie.

Complexity Analysis

Metric	Value
Time	O(n^3)
Space	O(n^2)

The time complexity of this approach is O(n^3) because of the Floyd-Warshall algorithm, which calculates the shortest paths for all pairs of cities. The space complexity is O(n^2) due to the need to store the shortest paths matrix for all city pairs.

What Interviewers Usually Probe

The candidate should show understanding of graph algorithms, specifically Floyd-Warshall or Dijkstra.
Look for the ability to identify the most efficient approach for all-pairs shortest path calculation.
Test if the candidate can optimize space and time by leveraging dynamic programming techniques.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem’s threshold condition can lead to incorrect results when counting neighbors.
Not considering the possibility of ties in the number of reachable neighbors can result in returning the wrong city.
Failing to apply the correct graph algorithm, leading to inefficiency or incorrect shortest path calculations.

Follow-up variants

Changing the graph representation (e.g., adjacency matrix vs adjacency list) could affect the implementation.
Increasing the number of cities could require considering optimizations in the graph algorithm used.
Allowing varying threshold values for different cities introduces a challenge in dynamic adjustment of the problem constraints.

FAQ

What is the time complexity of this problem?

The time complexity is O(n^3) due to the use of Floyd-Warshall’s algorithm for all-pairs shortest path computation.

Can this problem be solved using BFS or DFS?

While BFS and DFS can be used to find distances, they are not optimal for computing all-pairs shortest paths, making them inefficient for larger graphs.

What is the primary algorithmic pattern for solving this problem?

The primary pattern is state transition dynamic programming, using Floyd-Warshall or Dijkstra's algorithm to compute shortest paths.

How do I handle multiple cities with the same number of neighbors?

In case of a tie, return the city with the greatest number, as specified in the problem statement.

How can I optimize space when solving this problem?

You can reduce space complexity by using an adjacency list instead of an adjacency matrix, though the time complexity will still be O(n^3) in the worst case.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def findTheCity(
        self, n: int, edges: List[List[int]], distanceThreshold: int
    ) -> int:
        def dijkstra(u: int) -> int:
            dist = [inf] * n
            dist[u] = 0
            vis = [False] * n
            for _ in range(n):
                k = -1
                for j in range(n):
                    if not vis[j] and (k == -1 or dist[k] > dist[j]):
                        k = j
                vis[k] = True
                for j in range(n):
                    # dist[j] = min(dist[j], dist[k] + g[k][j])
                    if dist[k] + g[k][j] < dist[j]:
                        dist[j] = dist[k] + g[k][j]
            return sum(d <= distanceThreshold for d in dist)

        g = [[inf] * n for _ in range(n)]
        for f, t, w in edges:
            g[f][t] = g[t][f] = w
        ans, cnt = n, inf
        for i in range(n - 1, -1, -1):
            if (t := dijkstra(i)) < cnt:
                cnt, ans = t, i
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def findTheCity(
        self, n: int, edges: List[List[int]], distanceThreshold: int
    ) -> int:
        def dijkstra(u: int) -> int:
            dist = [inf] * n
            dist[u] = 0
            vis = [False] * n
            for _ in range(n):
                k = -1
                for j in range(n):
                    if not vis[j] and (k == -1 or dist[k] > dist[j]):
                        k = j
                vis[k] = True
                for j in range(n):
                    # dist[j] = min(dist[j], dist[k] + g[k][j])
                    if dist[k] + g[k][j] < dist[j]:
                        dist[j] = dist[k] + g[k][j]
            return sum(d <= distanceThreshold for d in dist)

        g = [[inf] * n for _ in range(n)]
        for f, t, w in edges:
            g[f][t] = g[t][f] = w
        ans, cnt = n, inf
        for i in range(n - 1, -1, -1):
            if (t := dijkstra(i)) < cnt:
                cnt, ans = t, i
        return ans

Continue Practicing

#1786 number of restricted paths from first to last node #787 cheapest flights within k stops #1976 number of ways to arrive at destination