# Destination City
**Difficulty:** EASY
[External](https://leetcode.com/problems/destination-city)
Canonical: https://scaleengineer.com/dsa/problems/destination-city
**Data structures:** Array, Hash Table, String
**Companies:** [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp)
---
## Problem
You are given the array `paths`, where `paths[i] = [cityAi, cityBi]` means there exists a direct path going from `cityAi` to `cityBi`. _Return the destination city, that is, the city without any path outgoing to another city._

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

**Example 1:**

**Input:** paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
**Output:** "Sao Paulo" 
**Explanation:** Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

**Example 2:**

**Input:** paths = [["B","C"],["D","B"],["C","A"]]
**Output:** "A"
**Explanation:** All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

**Example 3:**

**Input:** paths = [["A","Z"]]
**Output:** "Z"

**Constraints:**

* `1 <= paths.length <= 100`
* `paths[i].length == 2`
* `1 <= cityAi.length, cityBi.length <= 10`
* `cityAi != cityBi`
* All strings consist of lowercase and uppercase English letters and the space character.

# Approaches
## Brute Force using Nested Loops
This approach iterates through all possible destination cities and, for each one, checks if it's also a starting city by iterating through all the paths again. A city that is a destination but never a starting point is the final destination.
**Time:** O(N^2), where N is the number of paths. For each of the N paths, we iterate through all N paths again to check if the destination city is also a starting city. String comparisons take time proportional to the string length, but assuming it's bounded by a constant, the complexity is dominated by the nested loops. · **Space:** O(1), as we only use a few variables to keep track of the current candidate and a flag. No extra space proportional to the input size is used.
**Pros:** Simple to implement.; Requires no additional memory.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.
### Explanation
The algorithm works by considering each destination city from the `paths` list as a potential final destination. For each potential destination, we perform a search across all paths to see if this city ever appears as a starting city. If a potential destination is never found as a starting city after checking all paths, it is the true destination city, and we can return it immediately. This method is straightforward but inefficient due to the nested iteration over the list of paths.

```java
import java.util.List;

class Solution {
    public String destCity(List<List<String>> paths) {
        for (List<String> path : paths) {
            String dest = path.get(1);
            boolean isStartCity = false;
            for (List<String> otherPath : paths) {
                if (otherPath.get(0).equals(dest)) {
                    isStartCity = true;
                    break;
                }
            }
            if (!isStartCity) {
                return dest;
            }
        }
        return ""; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
*   Iterate through each path `p1` in `paths`. Let the destination of this path be `candidate_dest`.
*   Assume `candidate_dest` is the final destination. We use a boolean flag, say `isStartCity`, initialized to `false`.
*   Start a second, inner loop, iterating through each path `p2` in `paths`. Let the starting city of this path be `startCity`.
*   Compare `candidate_dest` with `startCity`. If they are the same, it means our candidate is also a starting city. Set `isStartCity` to `true` and break the inner loop.
*   After the inner loop finishes, check the flag `isStartCity`. If it's still `false`, it means `candidate_dest` was never found as a starting city. Thus, it is the final destination. Return `candidate_dest`.

## Efficient Approach using a Hash Set
This approach optimizes the search for starting cities by using a hash set. First, we collect all starting cities into a set. Then, we iterate through the paths again and check for a destination city that is not present in our set of starting cities. This city is the final destination.
**Time:** O(N), where N is the number of paths. The first loop to populate the hash set takes O(N) time (assuming average O(1) for set insertion). The second loop to find the destination also takes O(N) time (assuming average O(1) for set lookup). Therefore, the total time complexity is linear. · **Space:** O(N), where N is the number of paths. In the worst case, all N starting cities are unique and will be stored in the hash set. The space required is proportional to the number of paths and the length of the city names.
**Pros:** Significantly faster than the brute-force approach with linear time complexity.; The logic is clear and directly models the problem's condition.
**Cons:** Requires extra memory to store the set of starting cities.
### Explanation
The key insight is that the destination city is the only city that appears as a destination but never as a source. We can efficiently check this property using a hash set. The algorithm proceeds in two main steps: first, collect all source cities, and second, find a destination city that is not a source.

```java
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> startCities = new HashSet<>();
        // First pass: collect all starting cities
        for (List<String> path : paths) {
            startCities.add(path.get(0));
        }
        
        // Second pass: find the destination city that is not a starting city
        for (List<String> path : paths) {
            String dest = path.get(1);
            if (!startCities.contains(dest)) {
                return dest;
            }
        }
        
        return ""; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
*   Create a `HashSet<String>` called `startCities`.
*   Iterate through each path `[start, dest]` in `paths`. Add `start` to the `startCities` set.
*   Iterate through each path `[start, dest]` in `paths` again.
*   Check if `dest` is contained in the `startCities` set.
*   If `startCities.contains(dest)` is `false`, then `dest` is the destination city. Return `dest`.

# Solutions
### Java

```java
class Solution {
public
  String destCity(List<List<String>> paths) {
    Set<String> s = new HashSet<>();
    for (var p : paths) {
      s.add(p.get(0));
    }
    for (var p : paths) {
      if (!s.contains(p.get(1))) {
        return p.get(1);
      }
    }
    return "";
  }
}

```

### JavaScript

```javascript
/** * @param {string[][]} paths * @return {string} */ var destCity = function (
  paths,
) {
  const s = new Set();
  for (const [a, _] of paths) {
    s.add(a);
  }
  for (const [_, b] of paths) {
    if (!s.has(b)) {
      return b;
    }
  }
  return "";
};

```

### CPP

```cpp
class Solution {
public:
  string destCity(vector<vector<string>> &paths) {
    unordered_set<string> s;
    for (auto &p : paths) {
      s.insert(p[0]);
    }
    for (auto &p : paths) {
      if (!s.count(p[1])) {
        return p[1];
      }
    }
    return "";
  }
};

```

### Python

```python
class Solution:
    def destCity(self, paths: List[List[str]]) -> str: s = {a for a, _ in paths} return next(b for _, b in paths if b not in s)

```