Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

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

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
20 upvotes
Asked in companies
GoogleUberCitrix

Problem statement

You are given ‘N’ cities numbered from 0 to N-1 and ‘M’ edges. These cities are connected with undirected weighted edges. You are also given a positive integer, ‘distanceThreshold’.

Your task is to find the ‘city’ to which the minimum number of cities are reachable through some path whose distance is no more than the given ‘distanceThreshold’.

Note:

1. If multiple such cities exist, you have to find the city with the greatest number.

2. The distance of a path connecting two cities, ‘U’ and ‘V’, is the sum of the weight of the edges along that path.

3. The distance between two cities is the minimum of all possible path distances.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains three positive integers, ‘N’,  ‘M’, and ‘distanceThreshold’, as described in the problem statement.

The next ‘M’ lines of each test case contain three integers, ‘U’, ‘V’, and ‘W’ each, representing each edge of the graph.

The edge U V W represents an edge between vertices ‘U’ and ‘V’, having weight ‘W’.
Note:
The ‘edges’ will be passed to the function as an array of arrays. Each array will contain three integers, ‘U’, ‘V’, and ‘W’ in that order.
Output Format:
For each test case, print a single line containing a single integer denoting the required ‘city’ number, as described in the problem statement.

The output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
2 <= N <= 100
1 <= M <= (N * (N - 1)) / 2
0 <= U, V < N
1 <= W, distanceThreshold <= 100 

Where ‘T’ denotes the number of test cases, ‘N’ represents the number of cities, and ‘M’ denotes the number of edges.
‘U’, ‘V’, and ‘W’ denote the edge between city ‘U’ and ‘W’ having weight ‘W’.

Time limit: 1 sec.
Sample Input 1:
1
5 5 3
0 1 1
1 2 1
2 3 3
3 4 1
0 3 3
Sample Output 1:
4

altImage

Explanation for sample input 1:
The cities reachable to each city at a ‘distanceThreshold’ = 3 are as follows:
City 0 -> {City 1, City 2, City 3}
City 1 -> {City 0, City 2}
City 2 -> {City 0, City 1, CIty 3}
City 3 -> {City 0, City 2, City 3}
City 4 -> {City 3}
The city with the smallest number of neighbors at a ‘distanceThreshold’ = 3 is city 4 which has only 1 neighboring city.
Sample Input 2:
1
3 3 4
0 1 2
1 2 2
2 0 1
Sample Output 2:
2

altImage

Explanation for sample input 2:
The cities reachable to each city at a ‘distanceThreshold’ = 4 are as follows:
City 0 -> {City 1, City 2}
City 1 -> {City 0, City 2}
City 2 -> {City 0, City 1}
All three cities have 3 neighboring cities, So the answer must be the city with the greatest number that is city 2.
Hint

For each city calculate the number of reachable cities within the threshold, then search for the optimal city.

Approaches (2)
Dijkstra’s Algorithm

The idea here is to use Dijkstra’s algorithm to compute the distance between cities as the edge weights are non-negative. This algorithm fixed one node and treated it as a source and compute the distance of other nodes to the source. First, we need to make the adjacency list for the graph which contains for each city the city to which it is connected, and the edge weight of that edge. Now, we have to run Dijkstra’s algorithm for each city to find the distance of all other cities to it. Please read more about Dijkstra’s algorithm from Wikipedia.

 

Now, for each city, we have to calculate the reachable cities within the threshold. We can use the vector of pairs for the same, where the 1st element denotes the number of reachable cities to a particular city and the 2nd element represents the number of that city (that is used to break the tie). Sort the vector of pairs in a way that the 1st element of the vector will contain the desired output, and the second of the 1st element is the required city number. 

 

Steps:

  • Create a vector of pair of size N named adj for the adjacency list.
  • Run a loop from i = 0 to edges.size(), in each iteration:
    • Add {edges[i][1], edges[i][2]} in the adj[edges[i][0]].
    • Add {edges[i][0], edges[i][2]} in the adj[edges[i][1]].
  • Create a vector of pair named ans, where 1st element denotes the number of reachable cities to a particular city and 2nd element represents the number of that city.
  • Run a loop with variable i = 0 to N, in each iteration:
    • Call dijkstra(i, N, adj, distanceThreshold, ans), where i is the current city, N is the number of cities, adj is the adjacency list, distanceThreshold is the given value, and ans is the vector of pair for storing the answer.
    • This function will update ans with the number of cities reachable to city i.
  • Sort the vector ans with the help of the compare.
  • Finally, return ans[0].second.

bool compare(pair x, pair y):

  • This function is used to sort the vector of pairs.
  • If x.first != y.first, then return x.first < y.first.
  • Return x.second > y.second, because to break the tie we need the city with the greatest number first.

void dijkstra(int src, int n, vector of pair adj[], int distanceThreshold, vector of pair ans): 

  • This function is computing distance between src and all other cities.
  • Create a HashSet of type pair named findDist, where the 1st element denotes the distance between src and the city whose id is in the 2nd element.
  • Create a distance array of size N, and initialize it with INT_MAX.
  • Set distance[src] = 0, and insert {0, src} into the set.
  • Run a while loop until findDist becomes empty, in each iteration:
    • Declare a variable v, and initialize it with the second element of the top.
    • Remove the top element.
    • Run a loop to find all the direct connections of v, let u be its direct connections, and w be the edge weight in each iteration:
      • If distance[u] > distance[v] + w, then update distance[u] = distance[v] + w, and insert {distance[u], u} into the set findDist.
  • Declare a variable cnt = 0.
  • Run a loop from i = 0 to N, in each iteration:
    • If i != src and distance[i] <= distanceThreshold, then increase cnt by 1.
  • Add {cnt, i} into the vector of pairs ans.
Time Complexity

O(N * (MlogN)), where ‘N’ is the number of cities, and ‘M’ is the number of edges.

 

The time complexity of Dijkstra’s Algorithm is ‘M * logN’, and in the worst-case ‘M’ will be (N * (N-1))/2. Since we are calling Dijkstra’s algorithm for all the cities from 0 to N. Hence, overall time complexity will be O(N * (MlogN)).

Space Complexity

O(N ^ 2), where ‘N’ is the number of cities.

 

As we are creating an adjacency list for the graph, and in the worst case the graph will contain (N * (N - 1)) / 2 edges. Hence, we required an extra O(N ^ 2) space.

Code Solution
(100% EXP penalty)
Find the City With the Smallest Number of Neighbors at a Threshold Distance
All tags
Sort by
Search icon

Interview problems

Floyd–Warshall algorithm

import java.util.* ;
import java.io.*;
import java.util.ArrayList;
 
public class Solution {
public static int findTheCity(int n, ArrayList<ArrayList<Integer>> edges, int distanceThreshold) {
// city with minimum connected cities and distance should be less than
// threshold distance.
// if found more than 1 then city with greatest number
 
// to find all pair shortest path, we can use floyd warshall algo.
 
int[][] dist = new int[n][n];
for(int i = 0; i<n; i++){
Arrays.fill(dist[i], Integer.MAX_VALUE);
dist[i][i] = 0;
}
 
for(List<Integer> edge : edges){
int u = edge.get(0);
int v = edge.get(1);
int w = edge.get(2);
 
dist[u][v] = w;
dist[v][u] = w;
}
 
for(int k = 0; k<n; k++){
for(int i = 0; i<n; i++){
for(int j =0; j<n; j++){
if(dist[i][k] == Integer.MAX_VALUE || dist[k][j] == Integer.MAX_VALUE){
continue;
}
if(dist[i][j] > dist[i][k] + dist[k][j]){
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
 
int miniReachable = n;
int bestCity = -1;
for(int i = 0; i<n; i++){
int reachable = 0;
for(int j = 0; j<n; j++){
if(i != j && dist[i][j] <= distanceThreshold){
reachable++;
}
}
 
if(reachable <= miniReachable){
miniReachable = reachable;
bestCity = i;
}
}
 
return bestCity;
 
}
}
8 views
0 replies
0 upvotes

Interview problems

Python solution

from collections import *
from math import *

def findTheCity(n, edges, distanceThreshold):
    # Write your code here.
    num = float('inf')
    city = []
    for i in range(n):
        src = i
        dist = [float('inf')]*n
        dist[src] = 0
        for i in range(n-1):
            for j in range(len(edges)):
                u, v, w = edges[j]
                if dist[u]!=float('inf') and dist[u]+w<dist[v]:
                    dist[v] = dist[u]+w
                if dist[v]!=float('inf') and dist[v]+w<dist[u]:
                    dist[u] = dist[v]+w

        count = 0
        for k in range(n):
            if dist[k]<=distanceThreshold:
                count+=1
        #print(src, dist, count, num)
        if (count<=num):
            num = count
            city.append(src)
    #print(city)
    return max(city)
9 views
0 replies
0 upvotes

Interview problems

C++ || With explanation

#include <bits/stdc++.h> 

int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold){

 

    // Step 1 : Create a adj matrix

    vector<vector<int>> dist(n, vector<int>(n, 1e9));

 

    for(int i=0; i<edges.size(); i++){

 

        int u = edges[i][0];

        int v = edges[i][1];

        int w = edges[i][2];

 

        dist[u][v] = w;

        dist[v][u] = w;

 

    }

 

    // Step 3 : Set diagonal elements to 0

    for(int i=0; i<n; i++){

        dist[i][i] = 0;

    }

 

    // Apply floyd warshall algo

    for(int via=0; via<n; via++){

 

        for(int i=0; i<n; i++){

 

            for(int j=0; j<n; j++){

 

                if(dist[i][via] != 1e9 && dist[via][j] != 1e9){

                    dist[i][j] = min(dist[i][j], dist[i][via] + dist[via][j]);

                }

 

            }

 

        }

 

    }

 

    int cntCity = n;

    int city = -1;

 

    for(int i=0; i<n; i++){

 

        int cnt = 0;

 

        for(int j=0; j<n; j++){

 

            if(dist[i][j] <= distanceThreshold)

                cnt++;

 

        }

 

        if(cnt <= cntCity){

            cntCity = cnt;

            city = i;

        }

 

    }

 

    return city;

 

}

96 views
0 replies
1 upvote
profile

Interview problems

Find the City With the Smallest Number of Neighbors at a Threshold Distance.C++ Solution using Floyd Warshal. Easy solution.

#include <bits/stdc++.h> 

int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold) 

{

    // Write your code here 

    vector<vector<int>>dist(n,vector<int>(n,INT_MAX));

    for(auto it:edges){

        dist[it[0]][it[1]]=it[2];

        dist[it[1]][it[0]]=it[2];

    }

    for(int i=0;i<n;i++) dist[i][i]=0;

    for(int k=0;k<n;k++){

        for(int i=0;i<n;i++){

            for(int j=0;j<n;j++){

                if(dist[i][k]==INT_MAX||dist[k][j]==INT_MAX)

                    continue;

                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

            }

        }

    }

    int cntCity=n;

    int cityNo=-1;

    for(int city=0;city<n;city++){

        int cnt=0;

        for(int adjCity=0;adjCity<n;adjCity++){

            if(dist[city][adjCity]<=distanceThreshold) {

                cnt++;

            }

        }

        if(cnt<=cntCity){

            cntCity=cnt;

            cityNo=city;

        }

    }

    return cityNo;

}

86 views
0 replies
0 upvotes

Interview problems

Find the City With the Smallest Number of Neighbors at a Threshold Distance | C++ Solution

#include <vector>

#include <climits>

#include <iostream>

#include <algorithm>

using namespace std;

 

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {

    vector<vector<int>> distanceMatrix(n, vector<int>(n, INT_MAX));

 

    // Initialize the distance matrix with direct edges

    for (auto& edge : edges) {

        int u = edge[0];

        int v = edge[1];

        int w = edge[2];

        distanceMatrix[u][v] = w;

        distanceMatrix[v][u] = w;

    }

 

    // Floyd-Warshall algorithm to find the shortest distances between all pairs of cities

    for (int k = 0; k < n; ++k) {

        for (int i = 0; i < n; ++i) {

            for (int j = 0; j < n; ++j) {

                if (distanceMatrix[i][k] != INT_MAX && distanceMatrix[k][j] != INT_MAX) {

                    distanceMatrix[i][j] = min(distanceMatrix[i][j], distanceMatrix[i][k] + distanceMatrix[k][j]);

                }

            }

        }

    }

 

    int minNeighbours = INT_MAX;

    int city = -1;

 

    // Find the city with the minimum number of neighbors within the given distance threshold

    for (int i = 0; i < n; ++i) {

        int count = 0;

        for (int j = 0; j < n; ++j) {

            if (i != j && distanceMatrix[i][j] <= distanceThreshold) {

                count++;

            }

        }

        if (count <= minNeighbours) {

            minNeighbours = count;

            city = i;

        }

    }

 

    return city;

}

 

47 views
0 replies
0 upvotes

Interview problems

C++ dijkstras algo

#include <bits/stdc++.h> 

int solve(int source, int n, int k, vector<pair<int, int>> adj[]){
	vector<int> dis(n, INT_MAX);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, source});
	dis[source] = 0;

	while(!pq.empty()){
		int node = pq.top().second;
		int currDis = pq.top().first;
		pq.pop();

		for(auto i:adj[node]){
			int nextNode = i.first;
			int nextDis = i.second;

			if(nextDis + currDis < dis[nextNode]){
				dis[nextNode] = currDis + nextDis;
				pq.push({dis[nextNode], nextNode});
			}
		}
	}

	int count = 0;
	for(int i = 0; i < n; i++){
		if(dis[i] <= k){
			count++;
		}
	}

	return count;
}

int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold) 
{
	vector<pair<int, int>> adj[n];

	for(auto i:edges){
		adj[i[0]].push_back({i[1], i[2]});
		adj[i[1]].push_back({i[0], i[2]});
	}

	int ans = -1;
	int mini = INT_MAX;

	for(int i = 0; i < n; i++){
		int curr = solve(i, n, distanceThreshold, adj);
		if(curr <= mini){
			ans = i;
			mini = curr;
		}
	}

	return ans;
}
124 views
0 replies
0 upvotes

Interview problems

Graph || Floyd Marshal

import java.util.* ;

import java.io.*; 

import java.util.ArrayList;

 

public class Solution {

    public static int findTheCity(int n, ArrayList<ArrayList<Integer>> edges, int distanceThreshold) {

        /*

            Since here no source is given we need to find the cities with distance less than 

            threshold and return the max among those cities.

 

            1. We can apply floyd marshal algorithm to find the shortest path from each and 

            every node to each and every node

 

            Steps to apply floyd marshal

 

            1. We will have a dist matrix of size n*n for 0 based indexing

            2. All the diagonal elements will be 0.

            3. We will covert undirected graph to directed by making edges both sides

            4. We will update the given distance matrix with the given weights among nodes.

 

            5. After that we will go via each node and calculate the distance matrix.

            like a[i][j] = a[i][k] + a[k][j] if anyone of them is ifinity we can skip that

            iteration

 

            6. After our itration is done.

 

            7. We will have two variables one minCities count for each city and cityValue.

 

            8. We will try fo find the number of minCities within threshold for each node

            and update the minCity variable

 

            9. We will also update the city number

 

            10. Since we are going from 0 to n we will have the largest city number

            if num of mincities is same

 

        */

        

        // creating the dist matrix

        int[][] dist = new int[n][n];

 

        // updating with infinity

        for(int[] row: dist){

            Arrays.fill(row, (int)1e9);

        }

 

        // updting the diagonal to 0 as going from 1 to 1 will be 0

        for(int i=0; i<n; i++){

            dist[i][i] = 0;

        }

 

        int m = edges.size();

        // updating the given weights between nodes

        for(int i=0; i<m; i++){

            int u = edges.get(i).get(0);

            int v = edges.get(i).get(1);

            int distance = edges.get(i).get(2);

            dist[u][v] = distance;

            dist[v][u] = distance;

        }

 

        // aplying floyd marshal

        for(int k=0; k<n; k++){

            for(int i=0; i<n; i++){

                for(int j=0; j<n; j++){

                    if(dist[i][k]==1e9 || dist[k][j]==1e9){

                        continue;

                    }

                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

                }

            }

        }

 

        int minimumCityCount = Integer.MAX_VALUE;

        int cityNo = 0;

 

        //get mini city connected within threshold for each nodes

        for(int i=0; i<n; i++){

            int numOfCityConnected=0;

            for(int j=0; j<n; j++){

                if(dist[i][j]<=distanceThreshold){

                    numOfCityConnected++;

                }

            }

            if(numOfCityConnected<=minimumCityCount){

                minimumCityCount = numOfCityConnected;

                cityNo = i;

            }

        }

 

        return cityNo;

    }

}

62 views
0 replies
0 upvotes

Interview problems

BY DIJKSTRA'S

 int findCity(int n, int m, vector<vector<int>>& edges,int th)
    {
        vector<vector<int>> adj[n];
        for(int i=0;i<m;i++)
        {
            adj[edges[i][0]].push_back({edges[i][1],edges[i][2]});
            adj[edges[i][1]].push_back({edges[i][0],edges[i][2]});
        }
        vector<vector<int>> ans;
        for(int i=0;i<n;i++)
        {
            priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>> > pq;
            vector<int> dist(n,INT_MAX);
            
            dist[i]=0;
            pq.push({0,i});
            
            while(!pq.empty())
            {
                int parentDist=pq.top().first;
                int node=pq.top().second;
                pq.pop();
                
                for(int i=0;i<adj[node].size();i++)
                {
                    int data=adj[node][i][0];
                    int cost=adj[node][i][1];
                    int prevDist=dist[data];
                    dist[data]=min(dist[data],parentDist+cost);
                    if(prevDist!=dist[data])
                    {
                        pq.push({dist[data],data});
                    }
                }
            }
            ans.push_back(dist);
        }
        int maxC=n+1;
        int city=-1;
        for(int i=0;i<ans.size();i++)
        {
            int c=0;
            for(int j=0;j<ans[i].size();j++)
            {
                if(ans[i][j]<=th)
                {
                    ++c;
                }
            }
            if(maxC>=c)
            {
                maxC=c;
                city=i;
            }
        }
        return city;
    }
85 views
0 replies
1 upvote

Interview problems

Floyd Warshall in Java

import java.util.* ;
import java.io.*; 
import java.util.ArrayList;

public class Solution {
	public static int findTheCity(int n, ArrayList<ArrayList<Integer>> edges, int distanceThreshold) {
		// Write your code here
        int dis[][]=new int[n][n];
        for(int[] a:dis) Arrays.fill(a,(int)(1e9));
        for(int i=0;i<edges.size();i++){
          int u=edges.get(i).get(0), v=edges.get(i).get(1),w=edges.get(i).get(2);
          dis[u][v]=w;
          dis[v][u]=w;
          dis[u][u]=0;
          dis[v][v]=0;
        }
        for(int k=0;k<n;k++){
          for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
              if(dis[i][k]!=(int)(1e9) && dis[k][j]!=(int)(1e9)){
                dis[i][j]=Math.min(dis[i][j], dis[i][k]+dis[k][j]);
              }
            }
          }
        }
        int cityCount=n,city=-1;
        for(int i=0;i<n;i++){
          int currentCount=0;
          for(int j=0;j<n;j++){
            if(dis[i][j]<=distanceThreshold) currentCount++;
          }
          if(currentCount<=cityCount){
            cityCount=currentCount;
            city=i;
          }
        }
        return city;
	}
}
58 views
0 replies
0 upvotes

Interview problems

FLOYD WARSHALL's ALGO | C++:

int m=edges.size();

vector<vector<int>> adjMatrix(n, vector<int> (n , 1e9));

for(int i = 0; i < n; i++){

adjMatrix[i][i] = 0;

}

for(int i = 0; i < m; i++){

int u = edges[i][0];

int v = edges[i][1];

int wt = edges[i][2];

adjMatrix[u][v] = wt;

adjMatrix[v][u] = wt;

}

//Floyd Warshal Algorithm

for(int via = 0; via < n; via++){

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

if(adjMatrix[i][via] != 1e9 && adjMatrix[via][j] != 1e9){

adjMatrix[i][j] = min(adjMatrix[i][j], adjMatrix[i][via] + adjMatrix[via][j]);

}

}

}

}

int count = INT_MAX;

int ans = 0;

for(int i = 0; i < n; i++){

int cnt = 0;

for(int j = 0; j < n; j++){

if(i != j && adjMatrix[i][j] <= distanceThreshold){

cnt++;

}

}

if(cnt <= count){

count = cnt;

ans = i;

}

}

return ans;

datastructures

algorithms

207 views
0 replies
0 upvotes
Full screen
Console