Program to find all symmetric pairs in an array | FACE Prep

Program to find all symmetric pairs in an array | FACE Prep

Program to find all symmetric pairs in an array | FACE Prep

When working with pairs in an array, an interesting problem arises: finding symmetric pairs. Two pairs, (p, q) and (r, s), are symmetric when:

  • q is equal to r
  • p is equal to s

Example:

Consider the following 2D array:

Input:

arr [6][2] = { {1, 2}, {3, 4}, {5, 6}, {2, 1}, {4, 3}, {10, 11} }  

Output:

pgsqlCopyEdit{1,2} and {2,1} are symmetric  
{3,4} and {4,3} are symmetric  

Methods to Find Symmetric Pairs in an Array

There are two main approaches to solving this problem:

  1. Brute Force Approach – Using nested loops (O(n²) complexity)
  2. Efficient Approach – Using Hashing (O(n) complexity)

Let’s explore both methods with step-by-step explanations and code.


Method 1: Using Two Loops (Brute Force Approach)

Algorithm:

  1. Traverse the array using two nested loops.
  2. For each pair (p, q), check if (q, p) exists in the array.
  3. If found, print the symmetric pair.

Code:

cCopyEdit#include <stdio.h>

void findSymmetricPairs(int arr[][2], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i][0] == arr[j][1] && arr[i][1] == arr[j][0]) {
                printf("{%d, %d} and {%d, %d} are symmetric\n", arr[i][0], arr[i][1], arr[j][0], arr[j][1]);
            }
        }
    }
}

int main() {
    int arr[][2] = {{1, 2}, {3, 4}, {5, 6}, {2, 1}, {4, 3}, {10, 11}};
    int n = sizeof(arr) / sizeof(arr[0]);
    findSymmetricPairs(arr, n);
    return 0;
}

Time Complexity: O(n²)

Drawback: This method is inefficient for large datasets.


Method 2: Using Hashing (Optimized Approach)

To optimize the solution, we use a hash table (unordered map).

Algorithm:

  1. Traverse the array and insert each pair (p, q) into the hash table.
  2. For each new pair (r, s), check if s exists as a key in the hash table.
  3. If hash[s] == r, print the symmetric pair.
  4. Otherwise, store (p, q) in the hash table and continue.

Code:

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 1000

struct HashNode {
int key;
int value;
};

struct HashNode hashTable[TABLE_SIZE];

void insert(int key, int value) {
int index = key % TABLE_SIZE;
hashTable[index].key = key;
hashTable[index].value = value;
}

int search(int key, int value) {
int index = key % TABLE_SIZE;
return (hashTable[index].key == key && hashTable[index].value == value);
}

void findSymmetricPairs(int arr[][2], int n) {
for (int i = 0; i < n; i++) {
int first = arr[i][0];
int second = arr[i][1];

if (search(second, first)) {
printf("{%d, %d} and {%d, %d} are symmetric\n", first, second, second, first);
} else {
insert(first, second);
}
}
}

int main() {
int arr[][2] = {{1, 2}, {3, 4}, {5, 6}, {2, 1}, {4, 3}, {10, 11}};
int n = sizeof(arr) / sizeof(arr[0]);
findSymmetricPairs(arr, n);
return 0;
}

Time Complexity: O(n)

Advantage: Significantly faster than the brute force method for large datasets.


Comparison of Both Methods

ApproachTime ComplexitySpace ComplexitySuitability
Nested Loops (Brute Force)O(n²)O(1)Small datasets
Hashing (Optimized)O(n)O(n)Large datasets

Key Takeaways:

  • If n is small, the brute force method is acceptable.
  • If n is large, use hashing to optimize performance.

Similar Array-Based Problems to Solve

  • Find distinct elements in an array
  • Find non-repeating elements in an array
  • Check if two arrays are disjoint
  • Check if one array is a subset of another

Would you like solutions to these problems? Let me know.


Conclusion

Finding symmetric pairs in an array is a common problem in coding interviews and competitive programming. We explored two approaches:

  • Brute force approach (using two loops, O(n²))
  • Optimized approach (using hashing, O(n))

Using hashing significantly improves performance, making it the recommended solution for large datasets.

Program to find all symmetric pairs in an array | FACE Prep
c