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 arrayvoid 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 Codeint 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 approachimport 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 arraydef 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 Codeif __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 approachusing 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 arrayfunction 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 elementslet 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(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
