Given an array arr[] of size N consisting of distinct integers from range [0, N – 1] arranged in a random order. Also given a few pairs where each pair denotes the indices where the elements of the array can be swapped. There is no limit on the number of swaps allowed. The task is to find if it is possible to arrange the array in ascending order using these swaps. If possible then print Yes else print No.
Examples:
Input: arr[] = {0, 4, 3, 2, 1, 5}, pairs[][] = {{1, 4}, {2, 3}}
Output: Yes
swap(arr[1], arr[4]) -> arr[] = {0, 1, 3, 2, 4, 5}
swap(arr[2], arr[3]) -> arr[] = {0, 1, 2, 3, 4, 5}
Input: arr[] = {1, 2, 3, 0, 4}, pairs[][] = {{2, 3}}
Output: No
Approach: The given problem can be considered as a graph problem where N denotes the total number of nodes in the graph and each swapping pair denotes an undirected edge in the graph. We have to find out if it is possible to convert the input array in the form of {0, 1, 2, 3, …, N – 1}.
Let us call the above array as B. Now find out all the connected components of both the arrays and if the elements differ for at least one component then the answer is No else the answer is Yes.
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if the array elements// can be sorted with the given operationbool canBeSorted(int N, vector<int> a, int P, vector<pair<int, int> > vp){ // To create the adjacency list of the graph vector<int> v[N]; // Boolean array to mark the visited nodes bool vis[N] = { false }; // Creating adjacency list for undirected graph for (int i = 0; i < P; i++) { v[vp[i].first].push_back(vp[i].second); v[vp[i].second].push_back(vp[i].first); } for (int i = 0; i < N; i++) { // If not already visited // then apply BFS if (!vis[i]) { queue<int> q; vector<int> v1; vector<int> v2; // Set visited to true vis[i] = true; // Push the node to the queue q.push(i); // While queue is not empty while (!q.empty()) { int u = q.front(); v1.push_back(u); v2.push_back(a[u]); q.pop(); // Check all the adjacent nodes for (auto s : v[u]) { // If not visited if (!vis[s]) { // Set visited to true vis[s] = true; q.push(s); } } } sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); // If the connected component does not // contain same elements then return false if (v1 != v2) return false; } } return true;}// Driver codeint main(){ vector<int> a = { 0, 4, 3, 2, 1, 5 }; int n = a.size(); vector<pair<int, int> > vp = { { 1, 4 }, { 2, 3 } }; int p = vp.size(); if (canBeSorted(n, a, p, vp)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approach import java.io.*;import java.util.*;class GFG { // Function that returns true if the array elements // can be sorted with the given operation static boolean canBeSorted(int N, ArrayList<Integer> a, int p, ArrayList<ArrayList<Integer>> vp) { // To create the adjacency list of the graph ArrayList<ArrayList<Integer>> v = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < N; i++) { v.add(new ArrayList<Integer>()); } // Boolean array to mark the visited nodes boolean[] vis = new boolean[N]; // Creating adjacency list for undirected graph for (int i = 0; i < p; i++) { v.get(vp.get(i).get(0)).add(vp.get(i).get(1)); v.get(vp.get(i).get(1)).add(vp.get(i).get(0)); } for (int i = 0; i < N; i++) { // If not already visited // then apply BFS if (!vis[i]) { Queue<Integer> q = new LinkedList<>(); ArrayList<Integer> v1 = new ArrayList<Integer>(); ArrayList<Integer> v2 = new ArrayList<Integer>(); // Set visited to true vis[i] = true; // Push the node to the queue q.add(i); // While queue is not empty while (q.size() > 0) { int u = q.poll(); v1.add(u); v2.add(a.get(u)); // Check all the adjacent nodes for(int s: v.get(u)) { // If not visited if (!vis[s]) { // Set visited to true vis[s] = true; q.add(s); } } } Collections.sort(v1); Collections.sort(v2); // If the connected component does not // contain same elements then return false if(!v1.equals(v2)) { return false; } } } return true; } // Driver code public static void main (String[] args) { ArrayList<Integer> a = new ArrayList<Integer>(Arrays.asList(0, 4, 3, 2, 1, 5)); int n = a.size(); ArrayList<ArrayList<Integer>> vp = new ArrayList<ArrayList<Integer>>(); vp.add(new ArrayList<Integer>(Arrays.asList(1, 4))); vp.add(new ArrayList<Integer>(Arrays.asList(2, 3))); int p = vp.size(); if (canBeSorted(n, a, p, vp)) { System.out.println("Yes"); } else { System.out.println("No"); } }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation of the approachfrom collections import deque as queue# Function that returns true if the array elements# can be sorted with the given operationdef canBeSorted(N, a, P, vp): # To create the adjacency list of the graph v = [[] for i in range(N)] # Boolean array to mark the visited nodes vis = [False]*N # Creating adjacency list for undirected graph for i in range(P): v[vp[i][0]].append(vp[i][1]) v[vp[i][1]].append(vp[i][0]) for i in range(N): # If not already visited # then apply BFS if (not vis[i]): q = queue() v1 = [] v2 = [] # Set visited to true vis[i] = True # Push the node to the queue q.append(i) # While queue is not empty while (len(q) > 0): u = q.popleft() v1.append(u) v2.append(a[u]) # Check all the adjacent nodes for s in v[u]: # If not visited if (not vis[s]): # Set visited to true vis[s] = True q.append(s) v1 = sorted(v1) v2 = sorted(v2) # If the connected component does not # contain same elements then return false if (v1 != v2): return False return True# Driver codeif __name__ == '__main__': a = [0, 4, 3, 2, 1, 5] n = len(a) vp = [ [ 1, 4 ], [ 2, 3 ] ] p = len(vp) if (canBeSorted(n, a, p, vp)): print("Yes") else: print("No")# This code is contributed by mohit kumar 29 |
C#
// Include namespace systemusing System;using System.Collections.Generic;using System.Linq;using System.Collections;public class GFG{ // Function that returns true if the array elements // can be sorted with the given operation public static bool canBeSorted(int N, List<int> a, int p, List<List<int>> vp) { // To create the adjacency list of the graph var v = new List<List<int>>(); for (int i = 0; i < N; i++) { v.Add(new List<int>()); } // Boolean array to mark the visited nodes bool[] vis = new bool[N]; // Creating adjacency list for undirected graph for (int i = 0; i < p; i++) { v[vp[i][0]].Add(vp[i][1]); v[vp[i][1]].Add(vp[i][0]); } for (int i = 0; i < N; i++) { // If not already visited // then apply BFS if (!vis[i]) { var q = new LinkedList<int>(); var v1 = new List<int>(); var v2 = new List<int>(); // Set visited to true vis[i] = true; // Push the node to the queue q.AddLast(i); // While queue is not empty while (q.Count > 0) { var u = q.First(); q.RemoveFirst(); v1.Add(u); v2.Add(a[u]); // Check all the adjacent nodes foreach (int s in v[u]) { // If not visited if (!vis[s]) { // Set visited to true vis[s] = true; q.AddLast(s); } } } v1.Sort(); v2.Sort(); // If the connected component does not // contain same elements then return false if (!v1.SequenceEqual(v2)) { return false; } } } return true; } // Driver code public static void Main(String[] args) { var<int> a = new List<int>(new[] {0,4,3,2,1,5}); var n = a.Count; List<List<int>> vp = new List<List<int>>(); vp.Add(new List<int>(new[] {1,4})); vp.Add(new List<int>(new[] {2,3})); var p = vp.Count; if (GFG.canBeSorted(n, a, p, vp)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code is contributed by utkarshshirode02 |
Javascript
<script>// Javascript implementation of the approach // Function that returns true if the array elements // can be sorted with the given operation function canBeSorted(N,a,p,vp) { // To create the adjacency list of the graph let v= []; for(let i = 0; i < N; i++) { v.push([]); } // Boolean array to mark the visited nodes let vis = new Array(N); // Creating adjacency list for undirected graph for (let i = 0; i < p; i++) { v[vp[i][0]].push(vp[i][1]); v[vp[i][1]].push(vp[i][0]); } for (let i = 0; i < N; i++) { // If not already visited // then apply BFS if (!vis[i]) { let q = []; let v1 = []; let v2 = []; // Set visited to true vis[i] = true; // Push the node to the queue q.push(i); // While queue is not empty while (q.length > 0) { let u = q.shift(); v1.push(u); v2.push(a[u]); // Check all the adjacent nodes for(let s=0;s<v[u].length;s++) { // If not visited if (!vis[v[u][s]]) { // Set visited to true vis[v[u][s]] = true; q.push(v[u][s]); } } } v1.sort(function(c,d){return c-d;}); v2.sort(function(c,d){return c-d;}); // If the connected component does not // contain same elements then return false if(v1.toString()!=(v2).toString()) { return false; } } } return true; } // Driver code let a = [0, 4, 3, 2, 1, 5]; let n = a.length; let vp = []; vp.push([1, 4]); vp.push([2, 3]); let p = vp.length; if (canBeSorted(n, a, p, vp)) { document.write("Yes"); } else { document.write("No"); }// This code is contributed by unknown2108</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Method (Union-Find algorithm)
Approach
The given problem can be solve using the concept of Union-Find algorithm. We can consider each element of the array as a node in a graph, and the pairs as edges between the nodes. If two nodes are connected through a pair, it means that we can swap their values. The way is to check if we can form a connected graph of nodes, so that each node represents a number in the array, and each edge represents a pair that can be swapped. If we can form such a graph, it means that we can swap the elements to obtain a sorted array.
Algorithm
- Initialize a parent array of size N, where parent[i] represents the parent of the ith node in the graph. Initially, parent[i] = i for all i.
- Iterate through each pair, and for each pair (u, v), perform the following steps:
- a. Find the parent of u and v using the find() function.
- b. If the parents are not equal, set the parent of v to u using the union() function.
- Iterate through the array arr[], and for each element arr[i], check if its parent is equal to i. If there exists any element i such that parent[i] is not equal to i, it means that we cannot form a connected graph, and hence it is not possible to sort the array using the given pairs. Print “No” and return.
- If all elements have the same parent, it means that we can form a connected graph, and hence it is possible to sort the array using the given pairs. Print “Yes” and return.
C++
#include <iostream>#include <vector>using namespace std;// Find operation of Union-Find algorithmint find(int parent[], int i) { if (parent[i] == i) // If i is the parent of itself, return i return i; parent[i] = find(parent, parent[i]); // Path compression return parent[i];}// Union operation of Union-Find algorithmvoid union_sets(int parent[], int i, int j) { parent[find(parent, j)] = find(parent, i); // Connect the two sets by setting the parent of one to the other}// Function to check if it's possible to sort the array using the given pairsstring can_sort_array(vector<int> arr, vector<pair<int, int>> pairs) { int n = arr.size(); // Initialize the parent array with each node being a separate set int parent[n]; for (int i = 0; i < n; i++) parent[i] = i; // Merge the sets based on the given pairs for (auto p : pairs) union_sets(parent, p.first, p.second); // Check if each element is connected to its correct index for (int i = 0; i < n; i++) { if (find(parent, i) != find(parent, arr[i])) // If the parent of i is not the same as the parent of arr[i] return "No"; // Return "No" as the array cannot be sorted using the given pairs } return "Yes"; // If all elements are connected to their correct index, return "Yes"}int main() { vector<int> arr = {0, 4, 3, 2, 1, 5}; vector<pair<int, int>> pairs = {{1, 4}, {2, 3}}; cout << can_sort_array(arr, pairs) << endl; // Output: Yes arr = {1, 2, 3, 0, 4}; pairs = {{2, 3}}; cout << can_sort_array(arr, pairs) << endl; // Output: No return 0;} |
Python
def find(parent, i): if parent[i] == i: return i parent[i] = find(parent, parent[i]) # Path compression return parent[i]def union_sets(parent, i, j): parent[find(parent, j)] = find(parent, i)def can_sort_array(arr, pairs): n = len(arr) parent = [i for i in range(n)] # Initialize the parent array with each node being a separate set # Merge the sets based on the given pairs for p in pairs: union_sets(parent, p[0], p[1]) # Check if each element is connected to its correct index for i in range(n): if find(parent, i) != find(parent, arr[i]): return "No" return "Yes"arr = [0, 4, 3, 2, 1, 5]pairs = [(1, 4), (2, 3)]print(can_sort_array(arr, pairs)) # Output: Yesarr = [1, 2, 3, 0, 4]pairs = [(2, 3)]print(can_sort_array(arr, pairs)) # Output: No |
Java
//Java code for this approachimport java.util.*;class Main { // Find operation of Union-Find algorithm static int find(int[] parent, int i) { if (parent[i] == i) // If i is the parent of itself, return i return i; parent[i] = find(parent, parent[i]); // Path compression return parent[i]; } // Union operation of Union-Find algorithm static void unionSets(int[] parent, int i, int j) { parent[find(parent, j)] = find(parent, i); // Connect the two sets by setting the parent of one to the other } // Function to check if it's possible to sort the array using the given pairs static String canSortArray(List<Integer> arr, List<Pair<Integer, Integer>> pairs) { int n = arr.size(); // Initialize the parent array with each node being a separate set int[] parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; // Merge the sets based on the given pairs for (Pair<Integer, Integer> p : pairs) unionSets(parent, p.first, p.second); // Check if each element is connected to its correct index for (int i = 0; i < n; i++) { if (find(parent, i) != find(parent, arr.get(i))) // If the parent of i is not the same as the parent of arr[i] return "No"; // Return "No" as the array cannot be sorted using the given pairs } return "Yes"; // If all elements are connected to their correct index, return "Yes" } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList(0, 4, 3, 2, 1, 5); List<Pair<Integer, Integer>> pairs = Arrays.asList(new Pair<>(1, 4), new Pair<>(2, 3)); System.out.println(canSortArray(arr, pairs)); // Output: Yes arr = Arrays.asList(1, 2, 3, 0, 4); pairs = Arrays.asList(new Pair<>(2, 3)); System.out.println(canSortArray(arr, pairs)); // Output: No }}class Pair<A, B> { public A first; public B second; public Pair(A first, B second) { this.first = first; this.second = second; }}// Sundaram Singh |
Output
Yes No
Time complexity: O((m + n) log n).
Auxiliary Space: O(n), as it uses an array of length n to keep track of the parent of each node in the Union-Find data structure.
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!
