Categories

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

For a given bidirectional weighted graph, find the node (city) with the least number of nodes reachable within a given threshold.

Note: If there are multiple such nodes, then return the node with the highest value among them.

Time Complexity: O(n^3)

``````const findtheCity = (n, edges, threshold) => {

for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
adjMatrix[i][j] = (i === j) ? 0 : Number.MAX_VALUE;
}
}

for (const val of edges) {
}

let minNeighbours = Number.MAX_VALUE;
let neighbour;
for (let i = 0; i < n; i++) {
let currNeighbours = 0;

for (let j = 0; j < n; j++) {
currNeighbours++;
}
}

if (currNeighbours <= minNeighbours) {
minNeighbours = currNeighbours;
neighbour = i;
}
}

return neighbour;
};

const fw = (adjMatrix) => {
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
}
}

}
};

console.log(findtheCity(4, [
[0, 1, 3],
[1, 2, 1],
[1, 3, 4],
[2, 3, 1]
], 4)); // 3
``````

Demo