_1743. Restore the Array From Adjacent Pairs.md

1743. Restore the Array From Adjacent Pairs

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 27, 2024

Last updated : June 27, 2024

---

Related Topics : Array, Hash Table, Depth-First Search

Acceptance Rate : 74.76 %

---

Solutions

• m1743 v2.py
• m1743.py

Python

m1743 v2.py

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        mappings = defaultdict(list)
        starters = set()

        # Mapping
        for pair in adjacentPairs :
            mappings[pair[0]].append(pair[1])
            mappings[pair[1]].append(pair[0])
            
        # Find starter
        starter = -1
        for k, v in mappings.items() :
            if len(v) == 1 :
                starter = k
                break
        

            
        output = [starter]
        while len(output) <= len(adjacentPairs) :
            options = mappings[output[-1]]

            if len(options) <= 1 :
                output.append(options[0])
            elif output[-2] != options[0] :
                output.append(options[0])
            else :
                output.append(options[1])

        return output

m1743.py

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        mappings = defaultdict(List[int])
        starters = set()

        for pair in adjacentPairs :
            if pair[0] in mappings : 
                mappings[pair[0]].append(pair[1])
            else :
                mappings[pair[0]] = [pair[1]]
            
            if pair[1] in mappings :
                mappings[pair[1]].append(pair[0])
            else :
                mappings[pair[1]] = [pair[0]]

            if pair[0] in starters :
                starters.remove(pair[0])
            else :
                starters.add(pair[0])
                
            if pair[1] in starters :
                starters.remove(pair[1])
            else :
                starters.add(pair[1])

        output = [list(starters)[0]]
        while len(output) <= len(adjacentPairs) :
            options = mappings[output[-1]]

            if len(options) <= 1 :
                output.append(options[0])
            elif output[-2] != options[0] :
                output.append(options[0])
            else :
                output.append(options[1])

        return output