Sponsored
Sponsored
The idea is to determine which city does not have any outgoing paths. This can be done by keeping track of all cities that appear as the starting city of a path. The destination city is the one that is not in this set but appears as an ending city in the path list.
Time Complexity: O(n^2) due to linear checks within loops.
Space Complexity: O(n), where n is the number of cities.
1function destCity(paths) {
2 const startingCities = new Set();
3 for (let path of paths) {
4 startingCities.add(path[0]);
5 }
6 for (let path of paths) {
7 if (!startingCities.has(path[1])) {
8 return path[1];
9 }
10 }
11 return '';
12}This JavaScript solution utilizes a Set to keep track of cities appearing as starting points. We iterate over the paths to populate this Set and then determine the destination city by checking against it.
This approach involves counting occurrences of each city as an endpoint. The destination city will be the one whose occurrence as a destination is not matched by an occurrence as a start.
Time Complexity: O(n^2), since it includes iterating through paths multiple times.
Space Complexity: O(n) for storing city names.
1#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
string destCity(vector<vector<string>>& paths) {
unordered_map<string, int> cityCount;
for (auto& path : paths) {
cityCount[path[0]]++;
if (cityCount.find(path[1]) == cityCount.end()) {
cityCount[path[1]] = 0;
}
}
for (auto& path : paths) {
if (cityCount[path[1]] == 0) {
return path[1];
}
}
return "";
}In this C++ solution, we maintain a hashmap to count how many times a city appears as a start and ensure every destination is initialized in the map. The destination city will have a count of 0, indicating it never appears as a start.