View Destination City on LeetCode
Statistics
Time Spent Coding
2 minutes
Time Complexity
O(n) - In the worst case, every element in the input list will be visited twice, but constant multiples of n do not increase the growth rate, resulting in the O(n) time complexity.
Space Complexity
O(n) - In the worst case, every element in the input list will be stored twice, but constant multiples of n do not increase the growth rate, resulting in the O(n) space complexity.
Runtime Beats
99.93% of other submissions
Memory Beats
89.62% of other sumbissions
Explanation
The comments explain the program
Data Structures Used
Hash Table (Set) - An unordered container of non-repeating values.
Visual Examples
An array being transformed into a set, click to view
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
# Initialize sets to store all starting and ending cities
startings = set()
endings = set()
# Fill sets with corresponding elements from the input list
for s, e in paths:
startings.add(s)
endings.add(e)
# Iterate through all ending cities until one is not found within the starting cities set
for e in endings:
if e not in startings:
return e