Home » Technical Interview Questions » Hashing Interview Questions » Count of index pairs with equal elements in an array

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)

Count of index pairs with equal elements in an array

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 (n2). 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.

READ  Smallest Element Repeated Exactly K Times

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 ai and ay which will be counted as 1 pair. Similarly, ay and ax can also be pair. So, nC2 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.

READ  Find all permuted rows of a given row in a matrix

Space Complexity

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup