Package g1701_1800.s1743_restore_the_array_from_adjacent_pairs

Class Solution

java.lang.Object
g1701_1800.s1743_restore_the_array_from_adjacent_pairs.Solution
public class Solution extends Object
1743 - Restore the Array From Adjacent Pairs.<p>Medium</p> <p>There is an integer array <code>nums</code> that consists of <code>n</code> <strong>unique</strong> elements, but you have forgotten it. However, you do remember every pair of adjacent elements in <code>nums</code>.</p> <p>You are given a 2D integer array <code>adjacentPairs</code> of size <code>n - 1</code> where each <code>adjacentPairs[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that the elements <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> are adjacent in <code>nums</code>.</p> <p>It is guaranteed that every adjacent pair of elements <code>nums[i]</code> and <code>nums[i+1]</code> will exist in <code>adjacentPairs</code>, either as <code>[nums[i], nums[i+1]]</code> or <code>[nums[i+1], nums[i]]</code>. The pairs can appear <strong>in any order</strong>.</p> <p>Return <em>the original array</em> <code>nums</code><em>. If there are multiple solutions, return <strong>any of them</strong></em>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> adjacentPairs = [[2,1],[3,4],[3,2]]</p> <p><strong>Output:</strong> [1,2,3,4]</p> <p><strong>Explanation:</strong> This array has all its adjacent pairs in adjacentPairs. Notice that adjacentPairs[i] may not be in left-to-right order.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> adjacentPairs = [[4,-2],[1,4],[-3,1]]</p> <p><strong>Output:</strong> [-2,4,1,-3]</p> <p><strong>Explanation:</strong> There can be negative numbers. Another solution is [-3,1,4,-2], which would also be accepted.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> adjacentPairs = [[100000,-100000]]</p> <p><strong>Output:</strong> [100000,-100000]</p> <p><strong>Constraints:</strong></p> <ul> <li><code>nums.length == n</code></li> <li><code>adjacentPairs.length == n - 1</code></li> <li><code>adjacentPairs[i].length == 2</code></li> <li><code>2 <= n <= 10<sup>5</sup></code></li> <li><code>-10<sup>5</sup> <= nums[i], u<sub>i</sub>, v<sub>i</sub> <= 10<sup>5</sup></code></li> <li>There exists some <code>nums</code> that has <code>adjacentPairs</code> as its pairs.</li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • restoreArray

      public int[] restoreArray(int[][] adjacentPairs)