Given an array arr[] consisting of N integers, the task is to find the total number of unordered pairs (i, j) in the array such that arr[i] is equal to arr[j] and i < j for all subarrays of the given array.
Examples:
Input: arr[] = {1, 2, 1, 1}
Output: 6
Explanation: All subarrays of the given array of size greater than 1 are:
- {1, 2}: There are no such pairs satisfying the given criteria. Hence, the count of pairs for the current subarray is 0.
- {2, 1}: There are no such pairs satisfying the given criteria. Hence, the count of pairs for the current subarray is 0.
- {1, 1}: The pairs satisfying the given criteria are (0, 1). Hence, the count of pairs for the current subarray is 1.
- {1, 2, 1}: The pairs satisfying the given criteria are (0, 2). Hence, the count of pairs for the current subarray is 1.
- {2, 1, 1}: The pairs satisfying the given criteria are (1, 1). Hence, the count of pairs for the current subarray is 1.
- {1, 2, 1, 1}: The pairs satisfying the given criteria are (0, 2), (0, 3), and (2, 3). Hence, the count of pairs for the current subarray is 3.
Therefore, the total count from all the subarrays = 1 + 1 + 1 + 3 = 6.
Input: arr[] = {1, 2, 1, 3}
Output: 2
Naive Approach: The simplest approach to solve the given problem is to generate all possible subarrays of the size greater than 1, and find the sum of the count of pairs satisfying the given criteria for all possible subarrays of the given array.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by storing all positions corresponding to each distinct element in a Map and then, for each element, traverse the positions corresponding to that element and calculate the number of subarrays in which each pair occurs. Follow the steps below to solve the problem:
- Initialize a map M as having keys as a pair and values as a vector.
- Initialize another variable, say ans as 0 that stores the total count of pairs satisfying the given criteria.
- Traverse the given array arr[] using the variable i and append the value of i to the key M[arr[i]].
- Traverse the map M and perform the following steps:
- Initialize a vector, say V as the value corresponding to the current key.
- Initialize a variable, say sum as 0.
- Traverse the given vector V for each element V[j] add the value of (sum*(N – V[j])) to the variable ans and add the value (V[j] + 1) to the variable sum.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count all pairs (i, j)// such that arr[i] equals arr[j] in// all possible subarrays of the arrayvoid countPairs(vector<int> arr){ // Stores the size of the array int N = arr.size(); int ans = 0; // Stores the positions of all // the distinct elements map<int, vector<int> > M; // Append index corresponding // to arr[i] in the map for (int i = 0; i < arr.size(); i++) { M[arr[i]].push_back(i); } // Traverse the map M for (auto it : M) { vector<int> v = it.second; int sum = 0; // Traverse the array for (int j = 0; j < v.size(); j++) { // Update the value of // ans ans += sum * (N - v[j]); // Update the value of // the sum sum += v[j] + 1; } } // Print the value of ans cout << ans;}// Driver Codeint main(){ vector<int> arr = { 1, 2, 1, 1 }; countPairs(arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;import java.util.List;import com.google.common.collect.*;class GFG { // Function to count all pairs (i, j) // such that arr[i] equals arr[j] in // all possible subarrays of the array static void countPairs(int[] arr) { // Stores the size of the array int N = arr.length; int ans = 0; // Stores the positions of all // the distinct elements ListMultimap<Integer, Integer> M = ArrayListMultimap.create(); // Append index corresponding // to arr[i] in the map for (int i = 0; i < arr.length; i++) { M.put(arr[i], i); } // Traverse the map M for (var it: M.keySet()) { List<Integer> v = M.get(it); int sum = 0; // Traverse the array for (int j : v) { // Update the value of // ans ans += sum * (N - j); // Update the value of // the sum sum += j + 1; } } // Print the value of ans System.out.println(ans); } // Driver Code public static void main (String[] args) { int[] arr = { 1, 2, 1, 1 }; countPairs(arr); }}// This Code is contributed by ShubhamSingh10 |
Python3
# Python3 program for the above approach# Function to count all pairs (i, j)# such that arr[i] equals arr[j] in# all possible subarrays of the arraydef countPairs(arr): # Stores the size of the array N = len(arr) ans = 0 # Stores the positions of all # the distinct elements M = {} # Append index corresponding # to arr[i] in the map for i in range(len(arr)): if arr[i] in M: M[arr[i]].append(i) else: M[arr[i]] = [i] # Traverse the map M for key, value in M.items(): v = value sum1 = 0 # Traverse the array for j in range(len(v)): # Update the value of # ans ans += (sum1 * (N - v[j])) # Update the value of # the sum sum1 += v[j] + 1 # Print the value of ans print(ans)# Driver Codeif __name__ == '__main__': arr = [ 1, 2, 1, 1 ] countPairs(arr)# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program to implement above approachusing System;using System.Collections.Generic;class GFG{ // Function to count all pairs (i, j) // such that arr[i] equals arr[j] in // all possible subarrays of the array static void countPairs(int[] arr) { // Stores the size of the array int N = arr.Length; int ans = 0; // Stores the positions of all // the distinct elements Dictionary<int, List<int>> M = new Dictionary<int, List<int>>(); // Append index corresponding // to arr[i] in the map for (int i = 0 ; i < arr.Length ; i++) { if(!M.ContainsKey(arr[i])){ M.Add(arr[i], new List<int>()); } M[arr[i]].Add(i); } // Traverse the map M foreach (KeyValuePair<int, List<int>> it in M) { List<int> v = it.Value; int sum = 0; // Traverse the array foreach (int j in v) { // Update the value of // ans ans += sum * (N - j); // Update the value of // the sum sum += j + 1; } } // Print the value of ans Console.Write(ans); } // Driver Code public static void Main(string[] args){ int[] arr = new int[]{ 1, 2, 1, 1 }; countPairs(arr); }}// This code is contributed by subhamgoyal2014. |
Javascript
<script>// JavaScript program for the above approach// Function to count all pairs (i, j)// such that arr[i] equals arr[j] in// all possible subarrays of the arrayfunction countPairs(arr) { // Stores the size of the array let N = arr.length; let ans = 0; // Stores the positions of all // the distinct elements let M = new Map(); // Append index corresponding // to arr[i] in the map for (let i = 0; i < arr.length; i++) { if (M.has(arr[i])) { M.get(arr[i]).push(i); } else { M.set(arr[i], [i]) } } // Traverse the map M for (let it of M) { let v = it[1]; let sum = 0; // Traverse the array for (let j = 0; j < v.length; j++) { // Update the value of // ans ans += sum * (N - v[j]); // Update the value of // the sum sum += v[j] + 1; } } // Print the value of ans document.write(ans);}// Driver Codelet arr = [1, 2, 1, 1];countPairs(arr);</script> |
Output:
6
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
