When working with pairs in an array, an interesting problem arises: finding symmetric pairs. Two pairs, (p, q) and (r, s), are symmetric when:
Consider the following 2D array:
arr [6][2] = { {1, 2}, {3, 4}, {5, 6}, {2, 1}, {4, 3}, {10, 11} }
pgsqlCopyEdit{1,2} and {2,1} are symmetric
{3,4} and {4,3} are symmetric
There are two main approaches to solving this problem:
Let’s explore both methods with step-by-step explanations and 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;
}
Drawback: This method is inefficient for large datasets.
To optimize the solution, we use a hash table (unordered map).
#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;
}
Advantage: Significantly faster than the brute force method for large datasets.
Approach | Time Complexity | Space Complexity | Suitability |
---|---|---|---|
Nested Loops (Brute Force) | O(n²) | O(1) | Small datasets |
Hashing (Optimized) | O(n) | O(n) | Large datasets |
Would you like solutions to these problems? Let me know.
Finding symmetric pairs in an array is a common problem in coding interviews and competitive programming. We explored two approaches:
Using hashing significantly improves performance, making it the recommended solution for large datasets.