Identical Twins Editorial

Practice Problem Link: Identical Twins | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

For an array of integers nums, an identical twin is defined as pair (i, j) where nums[i] is equal to nums[j] and i < j. Given an array, find the number of identical twins.

Naive Approach

Using 2 nested loops, we iterate over all distinct pairs of elements and if they are equal we can increment the answer by one.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

int getIdenticalTwinsCount(vector<int> &arr) {
   int countIdenticalTwins = 0;
       for (int i = 0; i < arr.size(); i++) {
       for (int j = i + 1; j < arr.size(); j++) {
           if (arr[i] == arr[j]) {
               countIdenticalTwins++;
           }
       }
   }
   return countIdenticalTwins;
}

Java

class Solution {
   int getIdenticalTwinsCount (int[] arr) {
       int countIdenticalTwins = 0;
       for (int i = 0; i < arr.length; i++) {
           for (int j = i + 1; j < arr.length; j++) {
               if (arr[i] == arr[j]) {
                   countIdenticalTwins++;
               }
           }
       }
       return countIdenticalTwins;
   }
}

Optimal Approach

Observe that we want the sum of a number of possible pairs of an element of the same type. This hints at the use of hashing.

We can hash the frequency of all the numbers in the list using a hashmap and for each distinct number, we can form ^Nc₂ = (N * (N - 1) / 2) pairs of that particular number, where N is the frequency of that number in the list.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

int getIdenticalTwinsCount(vector<int> &arr) {
   unordered_map<int, int> frequency;
   for (auto x: arr) {
       frequency[x]++;
   }
   int identicalTwinCount = 0;
   for (auto x: frequency) {
       identicalTwinCount += (x.second * (x.second - 1) / 2);
   }
   return identicalTwinCount;
}

Java

class Solution {
   int getIdenticalTwinsCount (int[] arr) {
       HashMap<Integer, Integer> frequency = new HashMap<Integer, Integer>();
       for (int i = 0; i < arr.length; i++) {
           Integer val = frequency.get(arr[i]);
           if(val == null) {
               frequency.put(arr[i], 1);
           } else {
               frequency.put(arr[i], ++val);
           }
       }
       int identicalTwinCount = 0;
       for (Map.Entry<Integer, Integer> x: frequency.entrySet()) {
           identicalTwinCount += (x.getValue() * (x.getValue() - 1)) / 2;
       }
       return identicalTwinCount;
   }
}