Cracking the LeetCode

Introduction

I really wish I had the time to tackle one of these problems a day. I want to make it a goal for next year to do a whole month of daily challenges. Not going to happen in December with how busy it can get but I did find some time to sneak this little problem in. I haven't had time to work on my other side project lately and have been slammed at work doing .Net projects so decided to tackle this one in Python.

Problem

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

Examples

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]

Constraints

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui, vi <= 105
There exists some nums that has adjacentPairs as its pairs.

Process

Friday afternoon and my brain is running slowly. I decided to start by skipping the problem explanation and reading the examples instead. From what I can gather from the answers, I am expected to make integer arrays with unique elements, given an array of integer pairs. I assume each integer pair is a pairing of integers from the array I'm trying to make. My first thought was how easy this would be and I could just create a Set of all the numbers given in the 2D array. However, this doesn't take into account the order which I now realise is important. Based on the first example, [1,4,2,3] wouldn't be an acceptable answer because [1,4] isn't a pair and the pair [1,2] doesn't exist in my array.

My next thought is to add all the numbers in a set and THEN re-arrange until it matches all the pairs. I didn't get very far with this however as once I had my set, I couldn't figure out the best method to sort it. What I need is to find the extremities of the list first as these will only have one adjacent number and should only be found in a single pair. Just need a method to do this...

In comes the data structure of Graphs. These are data structures made up of vertices and edges. In this case, the vertices are each number in the array and the edges are what connect each pair. If we look at the first example, [[2,1],[3,4],[3,2]], this could be represented in a graph where 1 connects to 2, 2 connects to 1 and 3, 3 connects to 2 and 4, and 4 connects to 3.

As the vertices 1 and 4 each only have a single edge, they must make up the ends of the final array. Then, we can extrapolate from there and move along the "path" from either edge to make up the list (i.e. after 1 must be 2, then 3, then 4, or vice versa).

A graph can be made in Python with a dictionary, where each key is a vertice and it's items are the other vertices that connect to it. With this structure, we can find the end of the array with which keys in the dictionary only have an item length of 1. Finding the end would look like this:

uniq_nums = defaultdict(set)
for a, b in adjacentPairs:
    uniq_nums[b].add(a)
    uniq_nums[a].add(b)

for v, v2 in uniq_nums.items():
    if len(v2) == 1:
        break
end = v

Next, I just need to start at the end and go to the next number. I can check each item in the key and move to it if it's not equal to the previous item.

prev_v = False
length = len(adjacentPairs) + 1
while len(final_array) < length:
    for i in uniq_nums[v]:
        if i != prev_v:
            prev_v = v
            v = i
            final_array.append(v)
            break

Solution

Python

Here is the solution in Python:

def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
    uniq_nums = defaultdict(set)
    for a, b in adjacentPairs:
        uniq_nums[b].add(a)
        uniq_nums[a].add(b)

    for v, v2 in uniq_nums.items():
        if len(v2) == 1:
            break
    final_array = [v]
    prev_v = False
    length = len(adjacentPairs) + 1
    while len(final_array) < length:
        for i in uniq_nums[v]:
            if i != prev_v:
                prev_v = v
                v = i
                final_array.append(v)
                break
    return final_array

Conclusion

I haven't dealt with Graphs in a long time, and it's the first time since starting these LeetCode blogs so it took me some time to come to the solution. However, once I pieced it together, everything came easily. It's a bit disappointing seeing the Runtime and Memory results. Looking at other solutions that are quicker I notice they are using the same kind of solution so it must be very minor changes to improve. I also note that I completed this challenge almost a week after it came out as the daily so there are much more solutions to compare against.

Cracking the LeetCode - 1743

Restore the Array From Adjacent Pairs