We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Destination City

Number: 1547

Difficulty: Easy

Paid? No

Companies: Yandex, Amazon, Google, Meta, Apple, Yelp

Problem Description

Given an array paths where each element is a pair of cities [cityA, cityB] representing a one-way direct path from cityA to cityB, return the destination city. The destination city is defined as the city that does not have any outgoing paths.

Key Insights

  • The problem guarantees that the paths form a simple line without loops.
  • The destination city will never appear as a source city (i.e., the first element of any pair).
  • By gathering all source cities in a set, one can iterate through the destinations to find the one that is not in the source set.
  • The problem can be solved in O(n) time using a single pass over the list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of paths. Space Complexity: O(n), for storing the set of source cities.

Solution

The approach is to first create a set of all cities that appear as a source (the first element in each pair). Then, iterate through each pair and check if the destination city (the second element) is not in the set of source cities. Since the list of paths forms a simple linear graph without loops, exactly one city will satisfy this condition, and that is the destination city.

Code Solutions

# Function definition to find the destination city
def destCity(paths):
    # Set to store all source cities (cities with outgoing paths)
    source_cities = set()
    # Collect all source cities
    for path in paths:
        source_cities.add(path[0])
    
    # Iterate through each path to find the destination city
    for path in paths:
        # If a destination city is not in the set of source cities, it is the answer
        if path[1] not in source_cities:
            return path[1]
    # As per problem constraints, there is always one destination city
    return None

# Example usage:
paths = [["London", "New York"], ["New York", "Lima"], ["Lima", "Sao Paulo"]]
print(destCity(paths))  # Output: "Sao Paulo"
← Back to All Questions