Given an array pairs, find pairs [a , b] whose reverse [b , a] appears at another position. Return each match once, in the order it is discovered while scanning from left to right.
Write each answer as [max(a, b), min(a, b)]. Equal-number pairs are valid when they appear at least twice.
Example 1
Input: pairs = [[5, 5], [2, 8], [5, 5], [8, 2], [5, 5]]
Output: [[5, 5], [8, 2]]
Explanation: Two occurrences of [5, 5] form the first match, and [2, 8] with [8, 2] forms the second.
Example 2
Input: pairs = [[6, 6], [3, 9], [3, 9]]
Output: []
Explanation: [6, 6] appears only once, and the reverse [9, 3] is missing.
Brute Force Approach
Two pairs form a symmetric match when their numbers appear in reverse order. For each pair, search through the pairs that came before it. A match exists when the current pair’s first number equals an earlier pair’s second number, and its second number equals that pair’s first number.
Searching only earlier positions also prevents a pair from matching itself. This matters when both numbers are equal: the first occurrence has no matching copy yet, but a later occurrence can match the earlier one.
Once a match is found, arrange its numbers with the larger number first, keeping equal numbers unchanged. Before adding it, check whether the same answer is already in the result. This ensures that repeated occurrences produce only one answer.
Algorithm
Read the input pairs from left to right.
For each pair
[a, b], search the earlier pairs for[b, a].If no reverse is found, move to the next pair.
If a reverse is found, form
[max(a, b), min(a, b)].Add this answer only if it is not already in the result.
Return the result after processing every pair.
Dry Run
Find all symmetric pairs in an array - brute
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns each symmetric match once, in discovery order. vector<vector<int>> findSymmetricPairs(vector<vector<int>>& pairs) { vector<vector<int>> result; for (int i = 0; i < pairs.size(); i++) { int a = pairs[i][0]; int b = pairs[i][1]; bool reverseFound = false; // Search earlier positions so a pair cannot match itself. for (int j = 0; j < i; j++) { if (pairs[j][0] == b && pairs[j][1] == a) { reverseFound = true; break; } } if (reverseFound) { // Keep the larger number first; equal numbers stay unchanged. vector<int> candidate = {max(a, b), min(a, b)}; // Add each answer only once. if (find(result.begin(), result.end(), candidate) == result.end()) { result.push_back(candidate); } } } return result; }};// Driver codeint main() { vector<vector<int>> pairs = { {5, 5}, {2, 8}, {5, 5}, {8, 2}, {5, 5} }; // Create an instance of Solution. Solution sol; vector<vector<int>> result = sol.findSymmetricPairs(pairs); cout << "["; for (int i = 0; i < result.size(); i++) { if (i > 0) cout << ", "; cout << "[" << result[i][0] << ", " << result[i][1] << "]"; } cout << "]\n"; return 0;}Complexity Analysis
Time Complexity: O(N²), where N is the number of input pairs. Each pair may require a scan of the earlier pairs and another scan of the result.
Space Complexity: O(1) auxiliary space, excluding the result. The returned list can take O(N) space.
Optimal Approach
The brute force method repeatedly searches through earlier pairs. A hash set can remember those pairs and quickly check whether a reverse has appeared. For each current pair [a, b], search for [b, a] in the set.
The order of these actions matters: check for the reverse first, then store the current pair. This ensures that any match comes from an earlier position. It also handles equal-number pairs correctly. The first [a, a] is only stored; another occurrence can then match it.
A second hash set remembers answers already added to the result. Store these answers with the larger number first, keeping equal numbers unchanged. If a match appears again, this second set prevents another copy from being added. Appending answers as they are first found preserves the required order.
Algorithm
Keep a hash set for earlier input pairs and another for answers already added.
Read each pair
[a, b]from left to right.Check whether its reverse
[b, a]is in the set of earlier pairs.If the reverse exists, form
[max(a, b), min(a, b)].If this answer has not been added before, append it to the result and mark it as added.
After the reverse check, store the current pair in its original order.
Return the result.
Dry Run
Find all symmetric pairs in array - optimal
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns each symmetric match once, in discovery order. vector<vector<int>> findSymmetricPairs(vector<vector<int>>& pairs) { unordered_set<string> seen; unordered_set<string> added; vector<vector<int>> result; for (const auto& pair : pairs) { int a = pair[0]; int b = pair[1]; // A comma keeps the two numbers separate in each pair's key. string currentKey = to_string(a) + "," + to_string(b); string reverseKey = to_string(b) + "," + to_string(a); // Check earlier pairs before storing the current pair. if (seen.count(reverseKey)) { int larger = max(a, b); int smaller = min(a, b); string answerKey = to_string(larger) + "," + to_string(smaller); // Keep only the first discovery of this symmetric match. if (!added.count(answerKey)) { result.push_back({larger, smaller}); added.insert(answerKey); } } // Storing afterward prevents a single [a, a] from matching itself. seen.insert(currentKey); } return result; }};// Driver codeint main() { vector<vector<int>> pairs = { {5, 5}, {2, 8}, {5, 5}, {8, 2}, {5, 5} }; // Create an instance of Solution. Solution sol; vector<vector<int>> result = sol.findSymmetricPairs(pairs); cout << "["; for (int i = 0; i < result.size(); i++) { if (i > 0) cout << ", "; cout << "[" << result[i][0] << ", " << result[i][1] << "]"; } cout << "]\n"; return 0;}Complexity Analysis
Time Complexity: O(N) expected time, where N is the number of pairs. Each pair needs a constant number of hash-set operations, each taking expected O(1) time.
Space Complexity: O(N) auxiliary space for the two sets. The returned list can also take O(N) space.
Interview follow-up Questions
Yes. For example, [4, 7] with [7, 4], and [4, 9] with [9, 4], form two different matches. This is why complete pairs must be stored; a map that keeps only one second number for each first number could lose an earlier pair.
Be the first to add a comment.