Leetcode Problem 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

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

Leetcode Solutions

Floyd-Warshall Algorithm Approach

  1. Initialize a 2D array dist with dimensions n x n to store the shortest distances between all pairs of cities, setting the initial distances to infinity except for the diagonal (distance to self is 0).
  2. Update dist with the direct distances between cities provided in the edges array.
  3. Apply the Floyd-Warshall algorithm to compute the shortest paths between all pairs of cities.
  4. For each city, count the number of other cities that can be reached within the distanceThreshold.
  5. Find the city with the smallest number of reachable cities, and if there are multiple, return the one with the greatest number.
UML Thumbnail

Dijkstra's Algorithm Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...