Find all distinct symmetric pairs in an array efficiently
Given an array of pairs, each pairs two integer elements. Find the all distinct pairs in this array which is symmetric to each others. For example.
Example 1
Given pairs
{(1,2)
(2,3)
(2,1)
(2,4)
(4,2)}
Output
(1,2)
(2,4)
Because
[
(1, 2)
↗↙↘↖ symmetric pair
(2, 1)
(2, 4)
↗↙↘↖ symmetric pair
(4, 2)
]
Example 2:
Given pairs
{
(1,1)
(1,1)
(4,1)
(2,4)
(4,2)
}
Output
(2,4)
Because
[
(1, 1)
↗↙↘↖ Equal pair
(1, 1)
(Pair is repeating)
(2, 4)
↗↙↘↖ Symmetric pair
(4, 2)
]
Here given code implementation process.
/*
Java Program
Find all distinct symmetric pairs in an array efficiently
*/
import java.util.HashMap;
import java.util.HashSet;
public class DistinctPairs
{
// Find all the symmetric distinct pairs
public void symmetricPairs(int[][] arr, int n)
{
// Result indicator
boolean result = false;
// Collecting unique pair
HashMap < Integer, HashSet < Integer > > pairs =
new HashMap < Integer, HashSet < Integer > > ();
// Get the distinct pair combination
for (int i = 0; i < n; ++i)
{
if (pairs.containsKey(arr[i][0]))
{
// Add new value
pairs.get(arr[i][0]).add(arr[i][1]);
}
else
{
// Add new key
pairs.put(arr[i][0], new HashSet < Integer > ());
// Add first value
pairs.get(arr[i][0]).add(arr[i][1]);
}
}
// Find symmetric pairs
for (int key: pairs.keySet())
{
// iterate the pair element
for (int value: pairs.get(key))
{
if (value != key && pairs.containsKey(value)
&& pairs.get(value).contains(key))
{
// print pair
System.out.print("\n (" + key + "," + value + ")");
pairs.get(value).remove(key);
// Change result status
result = true;
}
}
}
if (result == false)
{
// When no resultant pair exists
System.out.print(" None \n");
}
}
public static void main(String[] arg)
{
DistinctPairs task = new DistinctPairs();
// Define pairs
int [][]arr =
{
{1,4},
{2,4},
{1,5},
{4,2},
{9,2},
{2,6},
{4,1},
{8,8},
{2,9},
{1,5},
};
int n = arr.length;
// Test case
task.symmetricPairs(arr, n);
}
}
Output
(1,4)
(2,4)
(2,9)
// Include header file
#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;
class DistinctPairs
{
public:
// Find all the symmetric distinct pairs
void symmetricPairs(int arr[][2], int n)
{
// Result indicator
bool result = false;
// Collecting unique pair
unordered_map < int, set < int > > pairs;
set < int > ::iterator value;
// Get the distinct pair combination
for (int i = 0; i < n; ++i)
{
if (pairs.find(arr[i][0]) != pairs.end())
{
// Add new value
pairs[arr[i][0]].insert(arr[i][1]);
}
else
{
// Add first value
pairs[arr[i][0]].insert(arr[i][1]);
}
}
for (auto &it: pairs)
{
for (value = it.second.begin(); value != it.second.end(); ++value)
{
if ( *value != it.first && pairs.find( *value) != pairs.end()
&& pairs[ *value].find(it.first) != pairs[ *value].end())
{
// print pair
cout << "\n (" << it.first << "," << *value << ")";
pairs[ *value].erase(it.first);
// Change result status
result = true;
}
}
}
if (result == false)
{
// When no resultant pair exists
cout << " None \n";
}
}
};
int main()
{
DistinctPairs task = DistinctPairs();
// Define pairs
int arr[][2] =
{
{1,4},
{2,4},
{1,5},
{4,2},
{9,2},
{2,6},
{4,1},
{8,8},
{2,9},
{1,5}
};
int n = sizeof(arr) / sizeof(arr[0]);
// Test case
task.symmetricPairs(arr, n);
return 0;
}
Output
(1,4)
(2,4)
(2,9)
// Include namespace system
using System;
using System.Collections.Generic;
public class DistinctPairs
{
// Find all the symmetric distinct pairs
public void symmetricPairs(int[,] arr, int n)
{
// Result indicator
Boolean result = false;
// Collecting unique pair
Dictionary < int, HashSet <int> > pairs =
new Dictionary <int, HashSet <int>> ();
// Get the distinct pair combination
for (int i = 0; i < n; ++i)
{
if (pairs.ContainsKey(arr[i,0]))
{
// Add new value
pairs[arr[i,0]].Add(arr[i,1]);
}
else
{
// Add new key
pairs.Add(arr[i,0], new HashSet<int>());
// Add first value
pairs[arr[i,0]].Add(arr[i,1]);
}
}
foreach(var entry in pairs)
{
foreach(int value in entry.Value)
{
if (value != entry.Key && pairs.ContainsKey(value)
&& pairs[value].Contains(entry.Key))
{
// print pair
Console.Write("\n (" + entry.Key + "," + value + ")");
pairs[value].Remove(entry.Key);
// Change result status
result = true;
}
}
}
if (result == false)
{
// When no resultant pair exists
Console.Write(" None \n");
}
}
public static void Main(String[] arg)
{
DistinctPairs task = new DistinctPairs();
// Define pairs
int[,] arr = {
{
1 , 4
} , {
2 , 4
} , {
1 , 5
} , {
4 , 2
} , {
9 , 2
} , {
2 , 6
} , {
4 , 1
} , {
8 , 8
} , {
2 , 9
} , {
1 , 5
} };
int n = arr.GetLength(0);
// Test case
task.symmetricPairs(arr, n);
}
}
Output
(1,4)
(2,4)
(2,9)
<?php
/*
Php Program
Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
// Find all the symmetric distinct pairs
public function symmetricPairs( & $arr, $n)
{
// Result indicator
$result = false;
// Collecting unique pair
$pairs = array();
// Get the distinct pair combination
for ($i = 0; $i < $n; ++$i)
{
if (array_key_exists($arr[$i][0], $pairs))
{
if ((array_search($arr[$i][1], $pairs[$arr[$i][0]])) === false)
{
$pairs[$arr[$i][0]][] = ($arr[$i][1]);
}
}
else
{
$pairs[$arr[$i][0]] = array();
$pairs[$arr[$i][0]][] = ($arr[$i][1]);
}
}
foreach($pairs as $key => $r)
{
foreach($pairs[$key] as $k => $value)
{
if ($value != $key &&
array_key_exists($value, $pairs)
&& in_array($key, $pairs[$value],True))
{
// print pair
echo "\n (". $key .",". $value .")";
if (($d = array_search($key, $pairs[$value])) !== false)
{
unset($pairs[$value][$d]);
}
// Change result status
$result = true;
}
}
}
if ($result == false)
{
// When no resultant pair exists
echo " None \n";
}
}
}
function main()
{
$task = new DistinctPairs();
// Define pairs
$arr = array(
array(1, 4),
array(2, 4),
array(1, 5),
array(4, 2),
array(9, 2),
array(2, 6),
array(4, 1),
array(8, 8),
array(2, 9),
array(1, 5)
);
$n = count($arr);
// Test case
$task->symmetricPairs($arr, $n);
}
main();
Output
(1,4)
(2,4)
(2,9)
/*
Node Js Program
Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
// Find all the symmetric distinct pairs
symmetricPairs(arr, n)
{
// Result indicator
var result = false;
// Collecting unique pair
var pairs = new Map();
// Get the distinct pair combination
for (var i = 0; i < n; ++i)
{
if (pairs.has(arr[i][0]))
{
// Add new value
pairs.get(arr[i][0]).add(arr[i][1]);
}
else
{
// Add new key
pairs.set(arr[i][0], new Set());
// Add first value
pairs.get(arr[i][0]).add(arr[i][1]);
}
}
for (let [key, record] of pairs)
{
for (let value of record.values())
{
if (value != key && pairs.has(value) && pairs.get(value).has(key))
{
// print pair
process.stdout.write("\n (" + key + "," + value + ")");
pairs.get(value).delete(key);
// Change result status
result = true;
}
}
}
if (result == false)
{
// When no resultant pair exists
process.stdout.write(" None \n");
}
}
}
function main()
{
var task = new DistinctPairs();
// Define pairs
var arr = [
[1, 4] ,
[2, 4] ,
[1, 5] ,
[4, 2] ,
[9, 2] ,
[2, 6] ,
[4, 1] ,
[8, 8] ,
[2, 9] ,
[1, 5]
];
var n = arr.length;
// Test case
task.symmetricPairs(arr, n);
}
main();
Output
(1,4)
(2,4)
(2,9)
# Python 3 Program
# Find all distinct symmetric pairs in an array efficiently
class DistinctPairs :
# Find all the symmetric distinct pairs
def symmetricPairs(self, arr, n) :
# Result indicator
result = False
# Collecting unique pair
pairs = dict()
i = 0
# Get the distinct pair combination
while (i < n) :
if (arr[i][0] in pairs.keys()) :
# Add new value
pairs.get(arr[i][0]).add(arr[i][1])
else :
# Add new key
pairs[arr[i][0]] = set()
# Add first value
pairs.get(arr[i][0]).add(arr[i][1])
i += 1
for key, record in pairs.items() :
for value in record :
if (value != key and value in pairs.keys()
and key in pairs.get(value)) :
# print pair
print("\n (", key ,",", value ,")", end = "")
pairs.get(value).remove(key)
# Change result status
result = True
if (result == False) :
# When no resultant pair exists
print(" None ")
def main() :
task = DistinctPairs()
# Define pairs
arr = [
[1, 4] ,
[2, 4] ,
[1, 5] ,
[4, 2] ,
[9, 2] ,
[2, 6] ,
[4, 1] ,
[8, 8] ,
[2, 9] ,
[1, 5]
]
n = len(arr)
# Test case
task.symmetricPairs(arr, n)
if __name__ == "__main__": main()
Output
( 1 , 4 )
( 2 , 9 )
( 2 , 4 )
# Ruby Program
# Find all distinct symmetric pairs in an array efficiently
class DistinctPairs
# Find all the symmetric distinct pairs
def symmetricPairs(arr, n)
# Result indicator
result = false
# Collecting unique pair
pairs = Hash.new
i = 0
# Get the distinct pair combination
while (i < n)
if (pairs.key?(arr[i][0]))
pairs[arr[i][0]].push(arr[i][1])
else
pairs[arr[i][0]] = []
pairs[arr[i][0]].push(arr[i][1])
end
i += 1
end
pairs.each{
|key,record|
for value in record do
if (value != key && pairs.key?(value) && pairs[value].include?(key))
# print pair
print("\n (", key ,",", value ,")")
pairs[value].delete(key)
# Change result status
result = true
end
end
}
if (result == false)
# When no resultant pair exists
print(" None \n")
end
end
end
def main()
task = DistinctPairs.new()
# Define pairs
arr = [
[1, 4] ,
[2, 4] ,
[1, 5] ,
[4, 2] ,
[9, 2] ,
[2, 6] ,
[4, 1] ,
[8, 8] ,
[2, 9] ,
[1, 5]
]
n = arr.length
# Test case
task.symmetricPairs(arr, n)
end
main()
Output
(1,4)
(2,4)
(2,9)
import scala.collection.mutable._;
/*
Scala Program
Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
// Find all the symmetric distinct pairs
def symmetricPairs(arr: Array[Array[Int]], n: Int): Unit = {
// Result indicator
var result: Boolean = false;
// Collecting unique pair
var pairs: Map[Int, Set[Int]] = Map();
var i: Int = 0;
// Get the distinct pair combination
while (i < n)
{
if (pairs.contains(arr(i)(0)))
{
// Add new value
pairs.get(arr(i)(0)).get.add(arr(i)(1));
}
else
{
// Add new key
pairs.addOne(arr(i)(0), Set());
// Add first value
pairs.get(arr(i)(0)).get.add(arr(i)(1));
}
i += 1;
}
for((key,record) <- pairs)
{
for (value <- record)
{
if (value != key && pairs.contains(value)
&& pairs.get(value).get.contains(key))
{
// print pair
print("\n (" + key + "," + value + ")");
pairs.get(value).get.remove(key);
// Change result status
result = true;
}
}
}
if (result == false)
{
// When no resultant pair exists
print(" None \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: DistinctPairs = new DistinctPairs();
// Define pairs
var arr: Array[Array[Int]] = Array(
Array(1, 4),
Array(2, 4),
Array(1, 5),
Array(4, 2),
Array(9, 2),
Array(2, 6),
Array(4, 1),
Array(8, 8),
Array(2, 9),
Array(1, 5)
);
var n: Int = arr.length;
// Test case
task.symmetricPairs(arr, n);
}
}
Output
(1,4)
(2,4)
(2,9)
import Foundation
/*
Swift 4 Program
Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
// Find all the symmetric distinct pairs
func symmetricPairs(_ arr: [
[Int]
], _ n: Int)
{
// Result indicator
var result: Bool = false;
// Collecting unique pair
var pairs = [Int: Set <Int> ]();
var i: Int = 0;
// Get the distinct pair combination
while (i < n)
{
if (pairs.keys.contains(arr[i][0]))
{
// Add new value
pairs[arr[i][0]]!.insert(arr[i][1]);
}
else
{
// Add new key
pairs[arr[i][0]] = Set <Int> ();
// Add first value
pairs[arr[i][0]]!.insert(arr[i][1]);
}
i += 1;
}
for (key, _) in pairs
{
for value in pairs[key]!
{
if (value != key && pairs.keys.contains(value)
&& pairs[value]!.contains(key))
{
// print pair
print("\n (", key, ",", value, ")", terminator: "");
pairs[value]!.remove(key);
// Change result status
result = true;
}
}
}
if (result == false)
{
// When no resultant pair exists
print(" None ");
}
}
}
func main()
{
let task: DistinctPairs = DistinctPairs();
// Define pairs
let arr: [[Int]] = [
[1, 4] ,
[2, 4] ,
[1, 5] ,
[4, 2] ,
[9, 2] ,
[2, 6] ,
[4, 1] ,
[8, 8] ,
[2, 9] ,
[1, 5]
];
let n: Int = arr.count;
// Test case
task.symmetricPairs(arr, n);
}
main();
Output
( 2 , 4 )
( 2 , 9 )
( 4 , 1 )
/*
Kotlin Program
Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
// Find all the symmetric distinct pairs
fun symmetricPairs(arr: Array < Array < Int >> , n: Int): Unit
{
// Result indicator
var result: Boolean = false;
// Collecting unique pair
var pairs = mutableMapOf<Int, MutableSet <Int>>();
var i: Int = 0;
// Get the distinct pair combination
while (i < n)
{
if (pairs.containsKey(arr[i][0]))
{
// Add new value
pairs.getValue(arr[i][0]).add(arr[i][1]);
}
else
{
// Add new key
pairs.put(arr[i][0], mutableSetOf <Int> ());
// Add first value
pairs.getValue(arr[i][0]).add(arr[i][1]);
}
i += 1;
}
// Find symmetric pairs
for (key in pairs.keys)
{
// iterate the pair element
for (value in pairs.getValue(key))
{
if (value != key && pairs.containsKey(value)
&& pairs.getValue(value).contains(key))
{
// print pair
print("\n (" + key + "," + value + ")");
pairs.getValue(value).remove(key);
// Change result status
result = true;
}
}
}
if (result == false)
{
// When no resultant pair exists
print(" None \n");
}
}
}
fun main(args: Array <String> ): Unit
{
var task: DistinctPairs = DistinctPairs();
// Define pairs
var arr: Array < Array <Int>> = arrayOf(
arrayOf(1, 4),
arrayOf(2, 4),
arrayOf(1, 5),
arrayOf(4, 2),
arrayOf(9, 2),
arrayOf(2, 6),
arrayOf(4, 1),
arrayOf(8, 8),
arrayOf(2, 9),
arrayOf(1, 5)
);
var n: Int = arr.count();
// Test case
task.symmetricPairs(arr, n);
}
Output
(1,4)
(2,4)
(2,9)
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment