This content originally appeared on DEV Community and was authored by Phoenix
Given an array of integers, and a number ‘sum’, print all unique pairs in the array whose sum is equal to ‘sum’.
Examples :
`Input : arr[] = {1, 5, 7, -1, 5}, sum = 6
Output : (1, 5), (7, -1)
Input : arr[] = {2, 5, 17, -1} sum = 7
Output : (2, 5)`
Approach - 1
- sort the array so that all duplicates resides side by side.
- when we found a pair
(a,b)if either a or b has duplicate values, we will only take first occurence of the duplicate value and skips the next occurences to avoid duplicate pairs. - now take 2 pointers left and right, left pointer starts from 0th index and right pointer from n-1th index.
- check for total 3 cases
- case-1
arr[left]+arr[right]==sum - we found a valid pair, so we print it and move both the pointers.
- and also check whether the curr pointer(left and right) is same as previous value, if yes move ahead without doing anything on these values.
- case-2
arr[left]+arr[right]<sum - move left pointer to get larger value
- case-3
arr[left]+arr[right]>sum - move right pointer to get smaller value
Code
vector<vector<int>> pairSum(vector<int> &arr, int s) {
int n = arr.size();
sort(arr.begin(), arr.end());
vector<vector<int>> pairs;
int i = 0;
int j = n - 1;
while (i < j) {
int sum = arr[i] + arr[j];
if (sum == s) {
pairs.push_back({arr[i], arr[j]});
i++;
j--;
// Skip duplicates for i
while (i < j && arr[i] == arr[i - 1]) {
i++;
}
// Skip duplicates for j
while (i < j && arr[j] == arr[j + 1]) {
j--;
}
} else if (sum < s) {
i++;
} else {
j--;
}
}
return pairs;
}
Time Complexity: O(N)+O(NlogN)
Approach - 2 Using Hashing
- create an hashmap that stores key-value pairs of elements and its frequencies.
- iterate through the elements
- for each element finds its complement and check whether it has been seen before.
- if it was seen before here 2 cases
- case-1 the element and its complement is same.. check its frequency. If the frequency is 1, print the pair since it can form a valid pair without duplicates.
- If the frequency is greater than 1, skip to avoid duplicates.
- case-2 If the current element and its complement are different
-
Check for the Complement:If the complement exists in the hashmap, it means we have previously encountered this complement. Avoiding Reverse Duplicates:- If the current element has been seen before (i.e., it’s already in the hashmap), you would be generating the pair in reverse order. To avoid printing the same pair twice (once as (a, b) and once as (b, a)), you only print the pair if it’s the first time you’re processing the current element.
- if not seen before moving ahead for searching to the next iteration, update the frequency of the element in the hashmap
// Function to print pairs with the given sum
void printPairs(int arr[], int n, int sum) {
// Store counts of all elements in map m
unordered_map<int, int> m;
// Traverse through all elements
for (int i = 0; i < n; i++) {
// Search if a pair can be formed with arr[i].
int rem = sum - arr[i];
if (rem == arr[i]) {
// Check if the complement is in the map and occurs only once
if (m.find(rem) != m.end() && m[rem] == 1) {
cout << "(" << rem << ", " << arr[i] << ")" << endl;
}
} else if (m.find(rem) != m.end() && m.find(arr[i]) == m.end()) {
// Check if the complement is in the map and the current element is not in the map
cout << "(" << rem << ", " << arr[i] << ")" << endl;
}
m[arr[i]]++; // Update the map with the current element's count
}
}
Time Complexity: O(N)
Space Complexity: O(N)
This content originally appeared on DEV Community and was authored by Phoenix
Print
Share
Comment
Cite
Upload
Translate
Updates
There are no updates yet.
Click the Upload button above to add an update.
APA
MLA
Phoenix | Sciencx (2024-09-21T18:36:48+00:00) Print all unique Pairs with given Sum. Retrieved from https://www.scien.cx/2024/09/21/print-all-unique-pairs-with-given-sum/
" » Print all unique Pairs with given Sum." Phoenix | Sciencx - Saturday September 21, 2024, https://www.scien.cx/2024/09/21/print-all-unique-pairs-with-given-sum/
HARVARDPhoenix | Sciencx Saturday September 21, 2024 » Print all unique Pairs with given Sum., viewed ,<https://www.scien.cx/2024/09/21/print-all-unique-pairs-with-given-sum/>
VANCOUVERPhoenix | Sciencx - » Print all unique Pairs with given Sum. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/09/21/print-all-unique-pairs-with-given-sum/
CHICAGO" » Print all unique Pairs with given Sum." Phoenix | Sciencx - Accessed . https://www.scien.cx/2024/09/21/print-all-unique-pairs-with-given-sum/
IEEE" » Print all unique Pairs with given Sum." Phoenix | Sciencx [Online]. Available: https://www.scien.cx/2024/09/21/print-all-unique-pairs-with-given-sum/. [Accessed: ]
rf:citation » Print all unique Pairs with given Sum | Phoenix | Sciencx | https://www.scien.cx/2024/09/21/print-all-unique-pairs-with-given-sum/ |
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.