Count of index pairs with equal elements in an array

Suppose, we have given an integer array. The problem “Count of index pairs with equal elements in an array” asks to find out the no of pair of indices (i,j) in such a way that arr[i]=arr[j] and i is not equal to j.

Example

arr[] = {2,3,1,2,3,1,4}

3

Explanation

Pairs of indices are: (0, 3), (1, 4), (2, 5)

arr[] = {3, 3, 1, 4}

1

Explanation

Pairs of indices are: (0, 1)

Algorithm

1. Declare a Map.
2. Traverse the array and count and store the frequency of each element into the map.
3. Set output to 0.
4. Traverse the map and get the frequency of each element from the map.
5. Do output += (VAL * (VAL – 1))/2, VAL is the frequency of each element.
6. Return output.

Explanation

We have given an array of integers, we have asked to find out the total no. of pairs present in an array such that their indices are not the same but the elements on those indices should be the same. So we are going to use a Hashing for it. Hashing is a better way than the brute force method in which we have to visit all those elements using extra time of O (n²). So we are avoiding that.

We will declare a map, picking up each element, count and store the frequency of each element into the map, if it is present already into the map, make a place for it, if it present already just increase its frequency by 1.

To use a combination formula, we have to count the frequency of each number. We are going to select several pairs that satisfy the given condition of equal elements but not their indices. We can assume that any number which is present in an array appears k times at any index up to kth index. Then pick any two indices a_i and a_y which will be counted as 1 pair. Similarly, a_y and a_x can also be pair. So, ⁿC₂ is the formula for finding out the number of pairs for which arr[i]=arr[j] also equal to x.

After the traversal of the array, and putting each element and its occurrence in a map, we will traverse the map, picking up each frequency of element and applying a formula on it, adding up with the output and store it in the output. We have to keep repeating it until we traverse all the elements and their frequencies and performing an operation on it. And at last, we will return that output.

C++ code to find count of index pairs with equal elements in an array

#include<iostream>
#include<unordered_map>

using namespace std;

int getNoOfPairs(int arr[], int n)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        MAP[arr[i]]++;

    int output = 0;
    for (auto it=MAP.begin(); it!=MAP.end(); it++)
    {
        int VAL = it->second;
        output += (VAL * (VAL - 1))/2;
    }
    return output;
}
int main()
{
    int arr[] = {2,3,1,2,3,1,4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getNoOfPairs(arr, n) << endl;
    return 0;
}

3

Java code to find count of index pairs with equal elements in an array

import java.util.HashMap;
import java.util.Map;

class countIndexPair
{
    public static int getNoOfPairs(int arr[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<>();

        for(int i = 0; i < n; i++)
        {
            if(MAP.containsKey(arr[i]))
                MAP.put(arr[i],MAP.get(arr[i]) + 1);
            else
                MAP.put(arr[i], 1);
        }
        int output=0;
        for(Map.Entry<Integer,Integer> entry : MAP.entrySet())
        {
            int VAL = entry.getValue();
            output += (VAL * (VAL - 1)) / 2;
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,1,2,3,1,4};
        System.out.println(getNoOfPairs(arr,arr.length));
    }
}

3

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.