Generate an array from given pairs of adjacent elements

0 0 7 minutes read

Given a 2D array arr[][] consisting of N pairs of integers such that the two elements in each row indicates that they are adjacent elements in the original array. The task is to construct an array with given pairs of adjacent elements of arr[].

Examples

Input: arr[] = {{5, 1 }, {3, 4 }, {3, 5}}
Output: 4 3 5 1
Explanation: The array can be constructed using the following operations:
Operation 1: The elements 4 and 1 have a single neighbor. Therefore, they can either be the first or last elements in the original array. Considering 4 to be the first element in the original array, A[] = {4}.
Operation 2: Place 3 adjacently to 4. Therefore, A[] = {4, 3}
Operation 3: Place 5 adjacently to 3. Therefore, A[] = {4, 3, 5}.
Operation 4: Place 1 as the last element in the array. Therefore, A[] = {4, 3, 5, 1}.

Input: arr[] = {{8, 11}, {-3, 6}, {-3, 8}}
Output: 6 -3 8 11

Approach: The problem can be solved using Hashing and DFS. Follow the steps below to solve the problem:

Initialize an adjacency list using a Map, say mp, to store assign neighbouring elements to each element.
Initialize a vector, say res, to store the original elements in the array.
Start creating the original array from the corner elements. Therefore, find the elements which have only one neighbor. This can be either the first or the last element of the original array.
Insert the obtained element in res.
Traverse through every element in the adjacency list and check if its neighbor(s) are visited or not.
Insert the unvisited neighbours in the vector res and traverse through all the neighbors of that element. Repeat step 5 till all elements are visited.
Return res.

Below is the implementation of the above approach:

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find original array
void find_original_array(vector<pair<int, int> >& A)
{
 
    // Map to store all neighbors for each element
    unordered_map<int, vector<int> > mp;
 
    // Vector to store original elements
    vector<int> res;
 
    // Stotrs which array elements are visited
    unordered_map<int, bool> visited;
 
    // Adjacency list to store neighbors
    // of each array element
    for (auto& it : A) {
 
        mp[it.first].push_back(it.second);
        mp[it.second].push_back(it.first);
    }
 
    auto it = mp.begin();
 
    // Find the first corner element
    for (; it != mp.end(); it++) {
        if (it->second.size() == 1) {
            break;
        }
    }
 
    // Stores first element of
    // the original array
    int adjacent = it->first;
  
 
    // Push it into the original array
    res.push_back(it->first);
 
    // Mark as visited
    visited[it->first] = true;
 
    // Traversing the neighbors and check
    // if the elements are visited or not
    while (res.size() != A.size() + 1) {
 
        // Traverse adjacent elements
        for (auto& elements : mp[adjacent]) {
 
            // If element is not visited
            if (!visited[elements]) {
 
                // Push it into res
                res.push_back(elements);
 
                // Mark as visited
                visited[elements] = true;
 
                // Update the next adjacent
                adjacent = elements;
            }
        }
    }
 
    // Print original array
    for (auto it : res) {
        cout << it << " ";
    }
}
 
// Driver Code
int main()
{
 
    // Given pairs of adjacent elements
    vector<pair<int, int> > A
        = { { 5, 1 }, { 3, 4 }, { 3, 5 } };
 
    find_original_array(A);
    return 0;
}

Java

// Java program of the above approach
import java.io.*;
import java.util.*;
 
class Pair {
    int first, second;
    Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class GFG {
    // Utility function to find original array
    static void find_original_array(List<Pair> A)
    {
 
        // Map to store all neighbors for each element
        @SuppressWarnings("unchecked")
        Map<Integer, List<Integer> > mp = new HashMap();
 
        // Vector to store original elements
        List<Integer> res = new ArrayList<Integer>();
 
        // Stotrs which array elements are visited
        @SuppressWarnings("unchecked")
        Map<Integer, Boolean> visited = new HashMap();
 
        // Adjacency list to store neighbors
        // of each array element
        for (Pair it : A) {
            List<Integer> temp;
            temp = (mp.containsKey(it.first))
                       ? mp.get(it.first)
                       : new ArrayList<Integer>();
            temp.add(it.second);
            mp.put(it.first, temp);
 
            temp = (mp.containsKey(it.second))
                       ? mp.get(it.second)
                       : new ArrayList<Integer>();
            temp.add(it.first);
            mp.put(it.second, temp);
        }
 
        int it = 0;
 
        // Find the first corner element
        for (Map.Entry<Integer, List<Integer> > entry :
             mp.entrySet()) {
            if (entry.getValue().size() == 1) {
                it = entry.getKey();
            }
        }
 
        // Stores first element of
        // the original array
        int adjacent = it;
 
        // Push it into the original array
        res.add(it);
 
        // Mark as visited
        visited.put(it, true);
 
        // Traversing the neighbors and check
        // if the elements are visited or not
        while (res.size() != A.size() + 1) {
 
            // Traverse adjacent elements
            for (int elements : mp.get(adjacent)) {
 
                // If element is not visited
                if (!visited.containsKey(elements)) {
 
                    // Push it into res
                    res.add(elements);
 
                    // Mark as visited
                    visited.put(elements, true);
 
                    // Update the next adjacent
                    adjacent = elements;
                }
            }
        }
 
        // Print original array
        for (int val : res) {
            System.out.print(val + " ");
        }
    }
    // Driver Code
    public static void main(String[] args)
    {
        @SuppressWarnings("unchecked")
        List<Pair> A = new ArrayList();
        A.add(new Pair(5, 1));
        A.add(new Pair(3, 4));
        A.add(new Pair(3, 5));
 
        find_original_array(A);
    }
}
 
// This code is contributed by jithin.

Python3

# Python3 program of the above approach
 
# Utility function to find original array
def find_original_array(A):
 
    # Map to store all neighbors for each element
    mp = [[] for i in range(6)]
 
    # Vector to store original elements
    res = []
 
    # Stotrs which array elements are visited
    visited = {}
 
    # A djacency list to store neighbors
    # of each array element
    for it in A:
        mp[it[0]].append(it[1])
        mp[it[1]].append(it[0])
 
    start = 0
 
    # Find the first corner element
    for it in range(6):
        if (len(mp[it]) == 1):
            start = it + 3
            break
 
    # Stores first element of
    # the original array   
    adjacent = start
 
    # Push it into the original array
    res.append(start)
 
    # Mark as visited
    visited[start] = True
 
    # Traversing the neighbors and check
    # if the elements are visited or not
    while (len(res) != len(A) + 1):
 
        # Traverse adjacent elements
        for elements in mp[adjacent]:
 
            # If element is not visited
            if (elements not in visited):
 
                # Push it into res
                res.append(elements)
 
                # Mark as visited
                visited[elements] = True
 
                # Update the next adjacent
                adjacent = elements
 
    # Print original array
    print(*res)
 
# Driver Code
if __name__ == '__main__':
 
    # Given pairs of adjacent elements
    A = [[5, 1],[ 3, 4],[ 3, 5]]
 
    find_original_array(A)
 
# This code is contributed by mohit kumar 29.

C#

// C# program of the above approach
using System;
using System.Collections.Generic;
 
public class Pair 
{
  public int first, second;
  public Pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
public class GFG
{
 
  // Utility function to find original array
  static void find_original_array(List<Pair> A)
  {
 
    // Map to store all neighbors for each element
    Dictionary<int,List<int>> mp = new Dictionary<int,List<int>>();
 
    // Vector to store original elements
    List<int> res = new List<int>();
 
    // Stotrs which array elements are visited
    Dictionary<int,bool> visited = new Dictionary<int,bool>();
 
    // Adjacency list to store neighbors
    // of each array element
    foreach (Pair it in A)
    {
      List<int> temp;
      temp = (mp.ContainsKey(it.first))
        ? mp[it.first]
        : new List<int>();
 
      temp.Add(it.second);
      if(!mp.ContainsKey(it.first))
        mp.Add(it.first, temp);
      else
        mp[it.first] = temp;
 
      temp = (mp.ContainsKey(it.second))
        ? mp[it.second]
        : new List<int>();
      temp.Add(it.first);
      if(!mp.ContainsKey(it.second))
        mp.Add(it.second, temp);
      else
        mp[it.second] = temp;
 
 
    }
 
    int It = 0;
 
    // Find the first corner element
    foreach (int key in mp.Keys)
    {
      if(mp[key].Count == 1)
      {
        It=key;
      }
    }
 
    // Stores first element of
    // the original array
    int adjacent = It;
 
    // Push it into the original array
    res.Add(It);
 
    // Mark as visited
    visited.Add(It, true);
 
    // Traversing the neighbors and check
    // if the elements are visited or not
    while (res.Count != A.Count + 1)
    {
 
      // Traverse adjacent elements
      foreach (int elements in mp[adjacent])
      {
 
        // If element is not visited
        if (!visited.ContainsKey(elements)) 
        {
 
          // Push it into res
          res.Add(elements);
 
          // Mark as visited
          visited.Add(elements, true);
 
          // Update the next adjacent
          adjacent = elements;
        }
      }
    }
 
    // Print original array
    foreach (int val in res)
    {
      Console.Write(val + " ");
    }
  }
 
  // Driver Code
  static public void Main (){
    List<Pair> A = new List<Pair>();
    A.Add(new Pair(5, 1));
    A.Add(new Pair(3, 4));
    A.Add(new Pair(3, 5));
 
    find_original_array(A);
  }
}
 
// This code is contributed by avanitrachhadiya2155

Javascript

<script>
 
// JavaScript program of the above approach
 
// Utility function to find original array
function find_original_array(A){
 
    // Map to store all neighbors for each element
    let mp = new Array(6).fill(0).map(()=>[])
 
    // Vector to store original elements
    let res = []
 
    // Stotrs which array elements are visited
    let visited = new Map();
 
    // A djacency list to store neighbors
    // of each array element
    for(let it of A){
        mp[it[0]].push(it[1])
        mp[it[1]].push(it[0])
    }
 
    let start = 0
 
    // Find the first corner element
    for(let it=0;it<6;it++){
        if (mp[it].length == 1){
            start = it + 3
            break
        }
    }
 
    // Stores first element of
    // the original array
    let adjacent = start
 
    // Push it into the original array
    res.push(start)
 
    // Mark as visited
    visited.set(start , true)
 
    // Traversing the neighbors and check
    // if the elements are visited or not
    while (res.length != A.length + 1){
 
        // Traverse adjacent elements
        for(let elements of mp[adjacent]){
 
            // If element is not visited
            if (!visited.has(elements)){
 
                // Push it into res
                res.push(elements)
 
                // Mark as visited
                visited.set(elements , true)
 
                // Update the next adjacent
                adjacent = elements
            }
        }
    }
 
    // Print original array
    for(let i of res){
        document.write(i," ");
    }
}
 
// Driver Code
 
// Given pairs of adjacent elements
let A = [[5, 1],[ 3, 4],[ 3, 5]]
 
find_original_array(A)
 
// This code is contributed by shinjanpatra
 
</script>

Output:

4 3 5 1

Time complexity: O(N²)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!