LeetCode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance Solution

Master LeetCode problem 1334 (Find the City With the Smallest Number of Neighbors at a Threshold Distance), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Medium

Dynamic Programming Graph Shortest Path

Problem Explanation

Explanation

To solve this problem, we can use the Floyd-Warshall algorithm to find the shortest path between each pair of cities. Then, for each city, we can count the number of cities that are reachable within the given distance threshold. Finally, we return the city with the smallest number of reachable cities, and if there are multiple cities with the same number of reachable cities, we return the city with the greatest number.

Initialize a 2D array distances of size n x n to store the shortest distances between cities.
Initialize the distances array with the weight of direct edges and set infinity for non-existent edges.
Run the Floyd-Warshall algorithm to update distances array with the shortest paths.
For each city, count the number of reachable cities within the distance threshold.
Return the city with the smallest number of reachable cities, and if there are multiple cities with the same number, return the city with the greatest number.

Time complexity: O(n^3) - for running Floyd-Warshall algorithm
Space complexity: O(n^2) - for the distances array

Solution Code

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] distances = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(distances[i], Integer.MAX_VALUE);
            distances[i][i] = 0;
        }
        
        for (int[] edge : edges) {
            distances[edge[0]][edge[1]] = edge[2];
            distances[edge[1]][edge[0]] = edge[2];
        }
        
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (distances[i][k] != Integer.MAX_VALUE && distances[k][j] != Integer.MAX_VALUE) {
                        distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                    }
                }
            }
        }
        
        int minCities = n, result = -1;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && distances[i][j] <= distanceThreshold) {
                    count++;
                }
            }
            if (count <= minCities) {
                minCities = count;
                result = i;
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1334 (Find the City With the Smallest Number of Neighbors at a Threshold Distance)?

This page provides optimized solutions for LeetCode problem 1334 (Find the City With the Smallest Number of Neighbors at a Threshold Distance) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1334 (Find the City With the Smallest Number of Neighbors at a Threshold Distance)?

The time complexity for LeetCode 1334 (Find the City With the Smallest Number of Neighbors at a Threshold Distance) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1334 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1334 in Java, C++, or Python.

Back to LeetCode Solutions