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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5char* destCity(char*** paths, int pathsSize, int* pathsColSize) {
6 bool outgoing[100] = {false};
7 char* cities[200];
8 int cityCount = 0;
9
10 for (int i = 0; i < pathsSize; i++) {
11 int startIndex = -1, endIndex = -1;
12 for (int j = 0; j < cityCount; j++) {
13 if (strcmp(cities[j], paths[i][0]) == 0) startIndex = j;
14 if (strcmp(cities[j], paths[i][1]) == 0) endIndex = j;
15 }
16 if (startIndex == -1) cities[cityCount++] = paths[i][0];
17 if (endIndex == -1) cities[cityCount++] = paths[i][1];
18
19 outgoing[startIndex] = true;
20 }
21
22 for(int i = 0; i < pathsSize; i++) {
23 char* destination = paths[i][1];
24 int j;
25 for (j = 0; j < cityCount; j++) {
26 if (strcmp(cities[j], destination) == 0 && !outgoing[j]) {
27 return destination;
28 }
29 }
30 }
31 return "";
32}
33This C solution uses an array to simulate a set to track which cities have outgoing paths. We iterate over the paths, storing cities in an array and marking those that appear as starting cities. Finally, we check which city does not appear as a starting city and return it as the destination.
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.
1using System;
2using System.Collections.Generic;
public class Solution {
public string DestCity(IList<IList<string>> paths) {
Dictionary<string, int> cityCount = new Dictionary<string, int>();
foreach (var path in paths) {
if (!cityCount.ContainsKey(path[0]))
cityCount[path[0]] = 0;
cityCount[path[0]]++;
if (!cityCount.ContainsKey(path[1]))
cityCount[path[1]] = 0;
}
foreach (var path in paths) {
if (cityCount[path[1]] == 0) {
return path[1];
}
}
return "";
}
}In the C# solution, a dictionary is used to count the number of times a city appears as the starting city. If a city only appears as a destination (count = 0), it is the destination city.