Total count of elements having frequency one in each Subarray

Given an array arr[] of length N, the task is to find the total number of elements that has frequency 1 in a subarray of the given array.

Examples:

Input: N = 3, arr[ ] = {2, 4, 2}
Output:  8
Explanation: All possible subarrays are 
{2}: elements with frequency one = 1.
{4}: elements with frequency one = 1.
{2}: elements with frequency one = 1.
{2, 4}: elements with frequency one = 2.
{4, 2}: elements with frequency one = 2.
{2, 4, 2}: elements with frequency one = 1 (i.e., only for 4).
Total count of elements = 1 + 1 + 1 + 2 + 2 + 1 = 8.

Input: N = 2, arr[ ] = {1, 1}
Output: 2
Explanation: All possible subarrays are 
{1}: elements with frequency one = 1.
{1, 1}: elements with frequency one = 0.
{1}: elements with frequency one = 1.
Total count of elements = 1 + 0 + 1 = 2.

Naive Approach: The simple idea is to calculate all the possible subarrays and for each subarray count the number of elements that are present only once in that subarray and add that count to the final answer.

• Initialize a variable count to 0. This variable will be used to store the total number of elements that have frequency 1 in a subarray of the given array.
• Iterate through all possible subarrays of the given array. For each subarray, do the following:
  • Create an unordered_map to store the frequency of each element in the subarray.
  • Iterate through all elements in the subarray. For each element, increment its frequency in the unordered_map.
  • Iterate through all elements in the unordered_map and check if their frequency is equal to 1. If so, increment the count variable by 1.
• Return the value of count.

Below is the implementation of the above approach:

8

Time Complexity: O(N³)
Auxiliary Space: O(N)

Efficient Approach: For the above approach, we will run out of time if the size of the array is very large. Therefore we have to optimize it. We can efficiently calculate the answer using Hashing based on the below idea:

Here we will evaluate the contribution done by each element to the final count. 

Say an element at index i has two other occurrences at j^th and k^th index (j < i < k). In this case, the element at i^th index has (i – j) * (k – i) number of choices to form a subarray where it is present only once.

Proof:

The i^th element can have (i – j) elements from its left [including itself] in any of the subarray where arr[i] has frequency 1.
Similarly, it can have (k – i) elements from its right [including itself] in any of the subarray satisfying the above condition.

So, from the basic principle of counting, we can see the total number of possible subarrays where arr[i] has frequency 1 is (i – j) * (k – i).

Follow the steps mentioned below to implement the idea:

• Initialize a map (say mp) to store the indices of occurrences of any element.
• Iterate through the array from i = 0 to N-1:
  • If arr[i] is arriving for the first time then insert -1 first. (because -1 will denote the first occurrence for ease of calculation)
  • Insert i in mp[arr[i]].
• Again for ease of calculation insert N at the end of each entry of the map.
• Now traverse through each element of the map and use the above formula to calculate the contribution of the element present in each index.
• Return the final count as the required answer.

Below is the implementation of the above idea.

8

Time Complexity: O(N)
Auxiliary Space: O(N)