Given an array arr[] consisting of N integers, the task for each array element is to find the absolute difference between the count of distinct elements to the left and the right of it in the given array arr[].
Examples:
Input: arr[] = {7, 7, 3, 2, 3}
Output: 2 2 0 1 2
Explanation:
Count of distinct elements that occur to the left of every index is given by [0, 0, 1, 1, 2] and the number of distinct elements that occur to the right of every index is [2, 2, 1, 0, 0]. Taking absolute difference of both gives the above output.Input: arr[] = {4, 3, 2, 3}
Output: 2 0 1 2
Naive Approach: The given problem can be solved using the Set Data Structure, the idea is to iterate over the range [0, i – 1] to find the count of distinct elements on the left of every element and similarly traverse the array over the range [i + 1, N – 1] to find the distinct elements on the right of every element. Follow the steps below to solve the given problem:
- Initialize an array res[] that stores the resultant absolute difference of distinct elements for each array element.
- Traverse the given array and for every element at index i perform the following operations:
- Iterate over the range [0, i – 1] and insert all the elements in the set, say S1.
- Iterate over the range [i + 1, N – 1] and insert all the elements in the set, say S2.
- Update the value of res[i] as the absolute difference of sizes of sets S1 and S2.
- After completing the above steps, print the array res[] 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 find the difference of// count of distinct elements to the// left and right for each array elementsvoid findDifferenceArray(int arr[], int N){ // Stores distinct array element // in the left and right set<int> S1; set<int> S2; // Traverse the array for (int i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (int j = 0; j < i; j++) { S1.insert(arr[j]); } // Insert all element to the right // in the set S2 for (int j = i + 1; j < N; j++) { S2.insert(arr[j]); } // Print the difference cout << abs((int)S1.size() - (int)S2.size()) << ' '; S1.clear(); S2.clear(); }}// Driver Codeint main(){ int arr[] = { 7, 7, 3, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); findDifferenceArray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.HashSet;class GFG{// Function to find the difference of// count of distinct elements to the// left and right for each array elementspublic static void findDifferenceArray(int arr[], int N){ // Stores distinct array element // in the left and right HashSet<Integer> S1 = new HashSet<Integer>(); HashSet<Integer> S2 = new HashSet<Integer>(); // Traverse the array for (int i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (int j = 0; j < i; j++) { S1.add(arr[j]); } // Insert all element to the right // in the set S2 for (int j = i + 1; j < N; j++) { S2.add(arr[j]); } // Print the difference System.out.print(Math.abs(S1.size() - S2.size()) + " "); S1.clear(); S2.clear(); }}// Driver Codepublic static void main(String args[]){ int arr[] = { 7, 7, 3, 2, 3 }; int N = arr.length; findDifferenceArray(arr, N);}}// This code is contributed by gfgking. |
Python3
# Python3 program for the above approach# Function to find the difference of# count of distinct elements to the# left and right for each array elementsdef findDifferenceArray(arr, N) : # Stores distinct array element # in the left and right S1 = set(); S2 = set(); # Traverse the array for i in range(N) : # Insert all element to the left # in the set S1 for j in range(i) : S1.add(arr[j]); # Insert all element to the right # in the set S2 for j in range(i + 1, N) : S2.add(arr[j]); # Print the difference print(abs(len(S1) - len(S2)),end=' '); S1.clear(); S2.clear();# Driver Codeif __name__ == "__main__" : arr = [ 7, 7, 3, 2, 3 ]; N = len(arr); findDifferenceArray(arr, N); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Function to find the difference of// count of distinct elements to the// left and right for each array elementspublic static void findDifferenceArray(int[] arr, int N){ // Stores distinct array element // in the left and right HashSet<int> S1 = new HashSet<int>(); HashSet<int> S2 = new HashSet<int>(); // Traverse the array for (int i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (int j = 0; j < i; j++) { S1.Add(arr[j]); } // Insert all element to the right // in the set S2 for (int j = i + 1; j < N; j++) { S2.Add(arr[j]); } // Print the difference Console.Write(Math.Abs(S1.Count - S2.Count) + " "); S1.Clear(); S2.Clear(); }} // Driver codepublic static void Main(String[] args){ int[] arr = { 7, 7, 3, 2, 3 }; int N = arr.Length; findDifferenceArray(arr, N);}}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the difference of // count of distinct elements to the // left and right for each array elements function findDifferenceArray(arr, N) { // Stores distinct array element // in the left and right let S1 = new Set(); let S2 = new Set(); // Traverse the array for (let i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (let j = 0; j < i; j++) { S1.add(arr[j]); } // Insert all element to the right // in the set S2 for (let j = i + 1; j < N; j++) { S2.add(arr[j]); } // Print the difference document.write(Math.abs(S1.size - S2.size) + ' '); S1.clear(); S2.clear(); } } // Driver Code let arr = [7, 7, 3, 2, 3]; let N = arr.length; findDifferenceArray(arr, N);// This code is contributed by Potta Lokesh </script> |
Output:
3 1 1 1 3
Time Complexity: O((N2)*log N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by storing the frequency of distinct elements on the left and the right for each array element and then find the resultant difference for each array element. Follow the steps below to solve the given problem:
- Initialize two unordered_map leftMap and rightMap to store the distinct elements on the left and right of every index respectively.
- Traverse the given array and insert all the array elements in the rightMap.
- Traverse the given array using the variable i and perform the following steps:
- Count distinct elements to the left of the current element(say countLeft) as the size of the map leftMap.
- Decrement the frequency of the current element from the map rightMap by 1.
- Count distinct elements to the right of the current element(say countRight) as the size of the map rightMap.
- Increment the frequency of the current element in the map leftMap by 1.
- Insert the value of the absolute difference of sizes of maps leftMap and rightMap.
- After completing the above steps, print the array res[] 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 find the difference of// count of distinct elements to the// left and right for each array elementsvoid findDifferenceArray(int arr[], int N){ // Stores the frequency of array // element to the left and the right unordered_map<int, int> leftMap, rightMap; // Stores the frequency of array // element in the map rightMap for (int i = 0; i < N; i++) { rightMap[arr[i]]++; } // Stores the resultant differences vector<int> res; // Traverse the array for (int i = 0; i < N; i++) { // Find the count in the left int countLeft = leftMap.size(); // Decrement the frequency if (rightMap[arr[i]] > 1) { rightMap[arr[i]]--; } else { rightMap.erase(arr[i]); } // Find the count in the left int countRight = rightMap.size(); // Insert the resultant difference res.push_back(abs(countRight - countLeft)); // Increment the frequency leftMap[arr[i]]++; } // Print the result for (auto& it : res) { cout << it << ' '; }}// Driver Codeint main(){ int arr[] = { 7, 7, 3, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); findDifferenceArray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the difference of // count of distinct elements to the // left and right for each array elements static void findDifferenceArray(int arr[], int N) { // Stores the frequency of array // element to the left and the right HashMap<Integer, Integer> leftMap = new HashMap<>(); HashMap<Integer, Integer> rightMap = new HashMap<>(); // Stores the frequency of array // element in the map rightMap for (int i = 0; i < N; i++) { if (rightMap.containsKey(arr[i])) rightMap.put(arr[i], rightMap.get(arr[i]) + 1); else rightMap.put(arr[i], 1); } // Stores the resultant differences Vector<Integer> res = new Vector<>(); // Traverse the array for (int i = 0; i < N; i++) { // Find the count in the left int countLeft = leftMap.size(); // Decrement the frequency if (rightMap.get(arr[i]) > 1) { rightMap.put(arr[i], rightMap.get(arr[i]) - 1); } else { rightMap.remove(arr[i]); } // Find the count in the left int countRight = rightMap.size(); // Insert the resultant difference res.add(Math.abs(countRight - countLeft)); // Increment the frequency if (leftMap.containsKey(arr[i])) leftMap.put(arr[i], leftMap.get(arr[i]) + 1); else leftMap.put(arr[i], 1); } // Print the result for (int it : res) { System.out.print(it + " "); } } // Driver Code public static void main(String[] args) { int arr[] = { 7, 7, 3, 2, 3 }; int N = arr.length; findDifferenceArray(arr, N); }}// This code is contributed by Rajput-Ji |
Python
# Function to find the difference of# count of distinct elements to the# left and right for each array elementsdef findDifferenceArray(arr, N): # Stores the frequency of array # element to the left and the right leftMap = {} rightMap = {} # Stores the frequency of array # element in the map rightMap for i in range(N): if arr[i] in rightMap: rightMap[arr[i]] += 1 else: rightMap[arr[i]] = 1 # Stores the resultant differences res = [] # Traverse the array for i in range(N): # Find the count in the left countLeft = len(leftMap) # Decrement the frequency if rightMap[arr[i]] > 1: rightMap[arr[i]] -= 1 else: del rightMap[arr[i]] # Find the count in the left countRight = len(rightMap) # Insert the resultant difference res.append(abs(countRight - countLeft)) # Increment the frequency if arr[i] in leftMap: leftMap[arr[i]] += 1 else: leftMap[arr[i]] = 1 # Print the result print(" ".join(str(x) for x in res))# Driver codeif __name__ == '__main__': arr = [7, 7, 3, 2, 3] N = len(arr) findDifferenceArray(arr, N) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to find the difference of // count of distinct elements to the // left and right for each array elements static void findDifferenceArray(int []arr, int N) { // Stores the frequency of array // element to the left and the right Dictionary<int, int> leftMap = new Dictionary<int, int>(); Dictionary<int, int> rightMap = new Dictionary<int, int>(); // Stores the frequency of array // element in the map rightMap for (int i = 0; i < N; i++) { if (rightMap.ContainsKey(arr[i])) rightMap[arr[i]] = rightMap[arr[i]] + 1; else rightMap.Add(arr[i], 1); } // Stores the resultant differences List<int> res = new List<int>(); // Traverse the array for (int i = 0; i < N; i++) { // Find the count in the left int countLeft = leftMap.Count; // Decrement the frequency if (rightMap[arr[i]] > 1) { rightMap[arr[i]] = rightMap[arr[i]] - 1; } else { rightMap.Remove(arr[i]); } // Find the count in the left int countRight = rightMap.Count; // Insert the resultant difference res.Add(Math.Abs(countRight - countLeft)); // Increment the frequency if (leftMap.ContainsKey(arr[i])) leftMap[arr[i]]= leftMap[arr[i]] + 1; else leftMap.Add(arr[i], 1); } // Print the result foreach (int it in res) { Console.Write(it + " "); } } // Driver Code public static void Main(String[] args) { int []arr = { 7, 7, 3, 2, 3 }; int N = arr.Length; findDifferenceArray(arr, N); }}// This code is contributed by Rajput-Ji |
Javascript
// JavaScript code for the above approachfunction findDifferenceArray(arr, N) { // Stores the frequency of array // element to the left and the right let leftMap = {}; let rightMap = {}; // Stores the frequency of array // element in the map rightMap for (let i = 0; i < N; i++) { if (rightMap[arr[i]]) { rightMap[arr[i]] += 1; } else { rightMap[arr[i]] = 1; } } // Stores the resultant differences let res = []; // Traverse the array for (let i = 0; i < N; i++) { // Find the count in the left let countLeft = Object.keys(leftMap).length; // Decrement the frequency if (rightMap[arr[i]] > 1) { rightMap[arr[i]] -= 1; } else { delete rightMap[arr[i]]; } // Find the count in the right let countRight = Object.keys(rightMap).length; // Insert the resultant difference res.push(Math.abs(countRight - countLeft)); // Increment the frequency if (leftMap[arr[i]]) { leftMap[arr[i]] += 1; } else { leftMap[arr[i]] = 1; } } // Print the result console.log(res.join(" "));}// Driver codelet arr = [7, 7, 3, 2, 3];let N = arr.length;findDifferenceArray(arr, N);// This code is contributed by phasing17. |
Output:
3 1 1 1 3
Time Complexity: O(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!
