O(N) Time; O(1) Space
Note: This is a heuristic solution based on python\'s hash(), so it is not complete. It works so long as none of the city names produce colliding hash codes. It
`Note: This is a heuristic solution based on python\'s hash(), so it is not complete. It works so long as none of the city names produce colliding hash codes. It is also linearly timebound given the constraints on the length of city names.`\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n$$O(N)$$ time and $$O(N)$$ space is trivial. I noticed an interesting property in that each city will appear twice except the `origin` and `destination` city. This reminded me of another problem https://leetcode.com/problems/single-number which has an optimal space solution of $$O(1)$$ without compromising time by leveraging a bitmask, so it seemed like something similar could be achieved here.\n\n\n# Approach\n*Let\'s use this example:*\n```python\npaths = [[\'London\', \'New York\'], [\'New York\', \'Lima\'], [\'Lima\', \'Sao Paulo\']]\n```\n1. Represent each city as an integer (In this case I used python\'s hash() function). This maps it to something similar to single-number problem linked above. From here on out numbers and cities mean the same thing.\n\n**Note**: *Only the last 8 bits of the hashes are shown for brevity.*\n```python\nLondon    -> ...11101101\nNew York  -> ...10110000\nLima      -> ...01101001\nSao Paulo -> ...00001000\n```\nSince all cities appear twice except `origin` and `destination`, by XOR\'ing all numbers together, we get **`origin_xor_destination`** that represents `origin ^ destination`. This is guaranteed by `x ^ x = 0`, so the repeating cities cancel out making it equivalent to xor\'ing only the non-repeating cities, `origin` and `destination`.\n```python\ncities = [hash(city) for path in paths for city in path]\norigin_xor_destination = reduce(int.__xor__, cities) # -> ...11100101\n```\n2. Great! We have a bitmask representing the first and last city in the linked list combined, but now we have a new problem: separating them. To do this, we need a bit that appears in either `origin` or `destination`, but not both. Any of the 1-bits in `origin_xor_destination` satisfies this condition based on the definition of XOR. \n```python\nLondon             -> ...11101101\nSao Paulo          -> ...00001000\nLondon ^ Sao Paulo -> ...11100101\n```\nI use `-origin_xor_destination & origin_xor_destination` because it is one line and efficient. Basically, take the bitwise negation (two\'s complement + 1) and & with itself. This captures the rightmost 1-bit (arbitrary, it could have been any of them, but this is an efficient way of getting one of them). \n```python\n-origin_xor_destination & original_xor_destination  -> ...00000001\n```\n\n3. Lets call this partition bit, `diff_bit`. We can use it to partition the cities into two sets, let\'s call these `include_diff_bit` and `exclude_diff_bit`. Any time we see a city that contains the bit, it will go in `include_diff_bit`, otherwise it goes in `exclude_diff_bit`.\n\n**The magic:** Remember, every city will appear twice except `origin` and `destination`. This means duplicates will once again cancel out out via `x ^ x = 0`. At the end, `origin` will be in one of the sets, and `destination` will be in the other set. Since they will be the only members of each bitmask set, each bitmask set effectively becomes `origin` or `destination`. *Ta-da!* We have decomposed our composite hash `origin_xor_destination` into `origin` and `destination`.\n\n4. Since we do not know whether `include_diff_bit` or `exclude_diff_bit` is the `destination` city, we can make one final pass through and compare the `path_destination` cities of all paths to `include_diff_bit` or `exclude_diff_bit` to identify the final node in the linked list. This works because the global `destination` must be one of the local `path_destinations`.\n\n\n# Complexity\n- Time complexity: $$O(N)$$, requires 3 passes through the paths.\n\n- Space complexity: $$O(1)$$, we need to persist four 32-bit bitmasks in memory: `origin_xor_destination`, `include_diff_bit`, `exclude_diff_bit`, and `diff_bit`.\n\n# Code\n```python\nclass Solution:\n    \n    def destCity(self, paths: List[List[str]]) -> str:\n\n        # 1: Find origin ^ destination.\n        origin_xor_destination = 0\n        for city_a, city_b in paths:\n            origin_xor_destination ^= hash(city_a)\n            origin_xor_destination ^= hash(city_b)\n\n        # 2: Find a bit belonging to origin or destination, but not both.\n        diff_bit = -origin_xor_destination & origin_xor_destination\n\n        include_diff_bit = exclude_diff_bit = 0\n        # 3: Split the cities up into the two sets.\n        for city_a, city_b in paths:\n            if hash(city_a) & diff_bit:\n                include_diff_bit ^= hash(city_a)\n            else:\n                exclude_diff_bit ^= hash(city_a)\n\n            if hash(city_b) & diff_bit:\n                include_diff_bit ^= hash(city_b)\n            else:\n                exclude_diff_bit ^= hash(city_b)\n        \n        # 4: Identify the destination city.\n        for _, path_destination in paths:\n            if hash(path_destination) == include_diff_bit or hash(path_destination) == exclude_diff_bit:\n                return path_destination\n\n```\n\nA more concise pythonic implementation leveraging generators:\n```\ndef get_city_hash(paths):\n    for city_hash in (hash(city) for path in paths for city in path):\n        yield city_hash\n\nclass Solution:\n\n    def destCity(self, paths: List[List[str]]) -> str:\n        \n        # 1: Find origin ^ destination.\n        origin_xor_destination = reduce(\n            int.__xor__, \n            get_city_hash(paths)\n        )\n\n        # 2: Find a bit belonging to origin or dedstination, but not both.\n        diff_bit = -origin_xor_destination & origin_xor_destination\n\n        # 3: Split the cities up into 2 sets.\n        origin_destination = [0,0]\n        for city_hash in get_city_hash(paths):\n            origin_destination[bool(city_hash & diff_bit)] ^= city_hash\n\n        # 4: Identify the destination city.\n        for path in paths:\n            if hash(path[1]) in origin_destination:\n                return path[1]\n```\n
['Bit Manipulation', 'Hash Function', 'Bitmask', 'Python3']