Restore the Array From Adjacent Pairs

Medium

Robinhood

1 view

Topics:

ArraysGraphs

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] = [u_i, v_i] indicates that the elements u_i and v_i 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.

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 <= 10⁵
-10⁵ <= nums[i], u_i, v_i <= 10⁵
There exists some nums that has adjacentPairs as its pairs.

Try coding it in LeetCode

Restore the Array From Adjacent Pairs

Medium

Robinhood

1 view

Topics:

ArraysGraphs

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] = [u_i, v_i] indicates that the elements u_i and v_i 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.

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 <= 10⁵
-10⁵ <= nums[i], u_i, v_i <= 10⁵
There exists some nums that has adjacentPairs as its pairs.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within the input pairs?
Is it guaranteed that the input array of adjacent pairs will always represent a valid, connected array that can be fully restored?
If there are multiple possible restored arrays, is any valid solution acceptable, or is there a specific ordering preference?
Can the input `adjacentPairs` array be empty or contain null values?
Is the length of the restored array guaranteed to be `n` where `n-1` is the length of the input `adjacentPairs` array?

Brute Force Solution

Approach

The brute force approach to reconstructing the array involves trying every possible starting number and checking if we can build a valid array. We'll keep track of visited numbers to avoid cycles and exhaustively explore all potential paths. It's like trying to solve a maze by trying every possible turn at each intersection.

Here's how the algorithm would work step-by-step:

Pick one of the numbers from the pairs as the potential start of the array.
Look at all pairs containing the starting number to find a possible second number.
If there are no such pairs, it means this starting number cannot lead to a valid array, so try a different starting number.
If a possible second number is found, add it to the array.
Now, look for pairs containing the second number (other than the pair that was used to find it).
If a third number is found, add it to the array and continue this process.
If at any point, you cannot find a valid next number from any of the remaining pairs (excluding the ones that lead to a previously visited number), this path is invalid, go back and try a different starting number or a different option for the second number.
Keep exploring different paths until a full array is reconstructed that uses all numbers exactly once.

Code Implementation

def restore_array_brute_force(adjacent_pairs):
    numbers = set()
    for pair in adjacent_pairs:
        numbers.add(pair[0])
        numbers.add(pair[1])

    for start_number in numbers:
        array = [start_number]
        visited = {start_number}
        current_number = start_number
        temp_pairs = adjacent_pairs[:]

        while len(array) < len(numbers):
            next_number = None
            pair_to_remove = None

            for pair_index, pair in enumerate(temp_pairs):
                if current_number in pair:
                    possible_next_number = pair[0] if pair[1] == current_number else pair[1]
                    # Prevents cycles by checking if the next number has already been visited
                    if possible_next_number not in visited:
                        next_number = possible_next_number
                        pair_to_remove = pair_index
                        break

            if next_number is None:
                break

            array.append(next_number)
            visited.add(next_number)
            current_number = next_number
            del temp_pairs[pair_to_remove]

        # Check if a valid array was found.
        if len(array) == len(numbers):
            return array

    return []

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible starting numbers (of which there are n from the adjacent pairs). For each starting number, it explores every possible path by considering the adjacent numbers as the next element in the array. In the worst-case scenario, it may need to try every possible permutation of the numbers to reconstruct the array, as incorrect choices lead to dead ends and require backtracking. Thus the total number of operations grows factorially with the number of elements, n, resulting in O(n!).

Space Complexity

O(N) – The described brute force approach uses recursion, and in the worst-case scenario, the algorithm might explore a path that visits almost all numbers before finding a valid or invalid solution. This could lead to a recursion depth proportional to the number of elements in the array, which is determined by the number of adjacent pairs. Since each recursive call adds a frame to the call stack, the maximum depth could be N, where N represents the total number of unique numbers in the array, leading to O(N) space for the call stack. Additionally, the algorithm would need to keep track of visited numbers to avoid cycles, and this set of visited numbers could potentially store all N numbers in the worst case, also contributing O(N) space.

Optimal Solution

Approach

The problem gives you pairs of numbers that were next to each other in an original sequence, but the sequence is scrambled. The optimal strategy is to reconstruct the sequence by finding the endpoints and tracing the connections between pairs.

Here's how the algorithm would work step-by-step:

First, find the starting number. This is the number that only appears in one pair because it's at the very beginning or end of the original sequence.
Now that you have the starting number, look for a pair that contains it. The other number in that pair is the next number in the sequence.
Keep repeating the process. Find the pair containing the last number you added to the sequence, and add the other number from that pair to the sequence.
Continue this until you've added all the numbers. You'll know you're done when you can't find any more pairs to extend the sequence.

Code Implementation

def restore_the_array_from_adjacent_pairs(adjacentPairs):
    graph = {}
    for pair in adjacentPairs:
        number1, number2 = pair
        if number1 not in graph:
            graph[number1] = []
        if number2 not in graph:
            graph[number2] = []
        graph[number1].append(number2)
        graph[number2].append(number1)

    # Find the start node, which has only one neighbor.
    start_node = None
    for node, neighbors in graph.items():
        if len(neighbors) == 1:
            start_node = node
            break

    result = []
    visited = set()
    current_node = start_node

    # Build the array by traversing the graph.
    while current_node is not None:
        result.append(current_node)
        visited.add(current_node)

        next_node = None
        
        # Find the next unvisited neighbor.
        if current_node in graph:
            for neighbor in graph[current_node]:
                if neighbor not in visited:
                    next_node = neighbor
                    break
        
        current_node = next_node

    return result

Big(O) Analysis

Time Complexity

O(n²) – Finding the starting number involves iterating through the adjacentPairs list, which can have up to n-1 pairs, and checking the frequency of each number, taking O(n) time. Reconstructing the array requires, in the worst case, iterating through the adjacentPairs list for each element to find the matching pair; since we have approximately n elements, this process takes O(n) for each element. Thus, in the worst case, we perform an O(n) operation n times. Therefore, the overall time complexity approximates n * n/2 which simplifies to O(n²).

Space Complexity

O(N) – The algorithm implicitly builds a hash map (or dictionary) to store the pairs and their connections. In the worst case, where all numbers are distinct, the hash map will store each number and its adjacent numbers, leading to space proportional to the number of unique numbers, which is bounded by N, the total number of numbers appearing in the pairs. Additionally, the restored array, which is the final output, requires space proportional to N to store all the numbers in the correct order. Therefore, the auxiliary space used is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array to signify no solution can be generated.
Input array with only one pair	Handle correctly by identifying the start and end based on the single pair provided.
Maximum number of pairs within allowed memory constraints	Ensure the used data structures (e.g., hash map) can scale efficiently to handle the maximum input size without memory issues.
Input represents a cyclic graph (no clear start or end)	Detect cycles and return an empty array as no valid linear restoration is possible.
Input contains pairs that form disconnected components	Return an empty array because the components cannot be connected into a single sequence
Input contains duplicate pairs	The algorithm should ignore duplicate pairs or handle them by overwriting in the adjacency list.
The graph structure does not result in a unique path	If multiple valid solutions exist, the algorithm can return any one of them, or indicate non-uniqueness.
Integer overflow when performing calculations on large numbers in the input	Use appropriate data types (e.g., long) to prevent overflow during computations.