Printing pairs in an Array
Given a pile of n pairs of elements in array arr[], containing 2*n elements, we have to print with the following conditions follow:
- If pair exists of the elements then print it.
- Else do not print the unpaired elements
Examples:
Input: n = 3, arr[] = {2, 1, 2, 3, 1, 3}
Output:
- Pair 1: 0 2
- Pair 2: 1 4
- Pair 3: 3 5
Explanation: We have a total of 2n = 6 elements. We need to find all possible ways to partition these 6 elements into pairs and give the index of paired items.
Approach: This can be solved with the following idea:
Using map data structure, store the indexes of each element, and print the index if a similar element occurs.
Steps involved in the implementation of the code:
- Loop through each element in the input vector.
- Check if the current element has already been paired up by checking its frequency in the unordered map.
- If the current element has not been paired up yet, find its matching element by looping through the remaining elements in the input vector.
- If a matching element is found, add the pair of elements to the output vector and decrement the frequency of the element in the unordered map.
- Repeat the above steps for all elements in the input vector.
Below are the steps involved in the implementation of the code
C++
// C++ code for the above approach: #include <iostream> #include <unordered_map> #include <vector> using namespace std; // Function to store pair of indexes vector<pair< int , int > > pairNums(vector< int > nums) { // Create an unordered map to store // the frequency of each element unordered_map< int , int > freq; // Count the frequency of each element for ( int i = 0; i < nums.size(); i++) { freq[nums[i]]++; } // Create a vector to store the pairs // of elements vector<pair< int , int > > pairs; // Pair up the elements for ( int i = 0; i < nums.size(); i++) { int num2 = nums[i]; // Check if the element has // already been paired if (freq[num2] > 0) { // Find a matching element int matchingNum = -1; for ( int j = i + 1; j < nums.size(); j++) { if (nums[j] == num2) { matchingNum = j; break ; } } // If a matching element is // found, pair them up if (matchingNum != -1) { pairs.push_back(make_pair(i, matchingNum)); freq[num2] -= 2; } } } // Return the pairs of elements return pairs; } // Driver code int main() { int n = 3; vector< int > nums = { 2, 1, 2, 3, 1, 3 }; // Function call vector<pair< int , int > > pairs = pairNums(nums); // Print the pairs of elements for ( int i = 0; i < pairs.size(); i++) { cout << "Pair " << i + 1 << ": " << pairs[i].first << " " << pairs[i].second << endl; } return 0; } |
Java
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class PairNums { // Function to store pair of indexes public static List<Map.Entry<Integer, Integer>> pairNums(List<Integer> nums) { // Create a map to store the frequency of each element Map<Integer, Integer> freq = new HashMap<>(); // Count the frequency of each element for ( int i = 0 ; i < nums.size(); i++) { int num = nums.get(i); freq.put(num, freq.getOrDefault(num, 0 ) + 1 ); } // Create a list to store the pairs of elements List<Map.Entry<Integer, Integer>> pairs = new ArrayList<>(); // Pair up the elements for ( int i = 0 ; i < nums.size(); i++) { int num2 = nums.get(i); // Check if the element has already been paired if (freq.get(num2) > 0 ) { // Find a matching element int matchingNum = - 1 ; for ( int j = i + 1 ; j < nums.size(); j++) { if (nums.get(j) == num2) { matchingNum = j; break ; } } // If a matching element is found, pair them up if (matchingNum != - 1 ) { pairs.add(Map.entry(i, matchingNum)); freq.put(num2, freq.get(num2) - 2 ); } } } // Return the pairs of elements return pairs; } // Driver code public static void main(String[] args) { List<Integer> nums = new ArrayList<>(); nums.add( 2 ); nums.add( 1 ); nums.add( 2 ); nums.add( 3 ); nums.add( 1 ); nums.add( 3 ); // Function call List<Map.Entry<Integer, Integer>> pairs = pairNums(nums); // Print the pairs of elements for ( int i = 0 ; i < pairs.size(); i++) { System.out.println( "Pair " + (i + 1 ) + ": " + pairs.get(i).getKey() + " " + pairs.get(i).getValue()); } } } |
Python3
# Python code for the above approach: # Function to store pair of indexes def pairNums(nums): # Create an unordered map to store # the frequency of each element freq = {} # Count the frequency of each element for i in range ( len (nums)): freq[nums[i]] = freq.get(nums[i], 0 ) + 1 # Create a vector to store the pairs # of elements pairs = [] # Pair up the elements for i in range ( len (nums)): num2 = nums[i] # Check if the element has # already been paired if freq[num2] > 0 : # Find a matching element matchingNum = - 1 for j in range (i + 1 , len (nums)): if nums[j] = = num2: matchingNum = j break # If a matching element is # found, pair them up if matchingNum ! = - 1 : pairs.append((i, matchingNum)) freq[num2] - = 2 # Return the pairs of elements return pairs # Driver code if __name__ = = '__main__' : n = 3 nums = [ 2 , 1 , 2 , 3 , 1 , 3 ] # Function call pairs = pairNums(nums) # Print the pairs of elements for i in range ( len (pairs)): print ( "Pair" , i + 1 , ":" , pairs[i][ 0 ], pairs[i][ 1 ]) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; using System.Collections.Generic; // Function to store pair of indexes public class Program { public static List<Tuple< int , int >> PairNums(List< int > nums) { // Create an unordered map to store // the frequency of each element Dictionary< int , int > freq = new Dictionary< int , int >(); // Count the frequency of each element for ( int i = 0; i < nums.Count; i++) { if (freq.ContainsKey(nums[i])) { freq[nums[i]]++; } else { freq[nums[i]] = 1; } } // Create a vector to store the pairs // of elements List<Tuple< int , int >> pairs = new List<Tuple< int , int >>(); // Pair up the elements for ( int i = 0; i < nums.Count; i++) { int num2 = nums[i]; // Check if the element has // already been paired if (freq[num2] > 0) { // Find a matching element int matchingNum = -1; for ( int j = i + 1; j < nums.Count; j++) { if (nums[j] == num2) { matchingNum = j; break ; } } // If a matching element is // found, pair them up if (matchingNum != -1) { pairs.Add( new Tuple< int , int >(i, matchingNum)); freq[num2] -= 2; } } } // Return the pairs of elements return pairs; } // Driver code public static void Main( string [] args) { //int n = 3; List< int > nums = new List< int > { 2, 1, 2, 3, 1, 3 }; List<Tuple< int , int >> pairs = PairNums(nums); for ( int i = 0; i < pairs.Count; i++) { Console.WriteLine( "Pair " + (i + 1) + ": " + pairs[i].Item1 + " " + pairs[i].Item2); } } } |
Javascript
// Nikunj Sonigara // Function to store pair of indexes function pairNums(nums) { // Create a map to store the frequency of each element const freq = new Map(); // Count the frequency of each element for (let i = 0; i < nums.length; i++) { const num = nums[i]; freq.set(num, (freq.get(num) || 0) + 1); } // Create an array to store the pairs of elements const pairs = []; // Pair up the elements for (let i = 0; i < nums.length; i++) { const num2 = nums[i]; // Check if the element has already been paired if (freq.get(num2) > 0) { // Find a matching element let matchingNum = -1; for (let j = i + 1; j < nums.length; j++) { if (nums[j] === num2) { matchingNum = j; break ; } } // If a matching element is found, pair them up if (matchingNum !== -1) { pairs.push([i, matchingNum]); freq.set(num2, freq.get(num2) - 2); } } } // Return the pairs of elements return pairs; } // Driver code function main() { const nums = [2, 1, 2, 3, 1, 3]; // Function call const pairs = pairNums(nums); // Print the pairs of elements for (let i = 0; i < pairs.length; i++) { console.log(`Pair ${i + 1}: ${pairs[i][0]} ${pairs[i][1]}`); } } main(); |
Output
Pair 1: 0 2 Pair 2: 1 4 Pair 3: 3 5
Time complexity: O(N*2)
Auxiliary Space: O(N)
Contact Us