Whole rely of components having frequency one in every Subarray

Given an array arr[] of size N, the duty is to search out the entire variety of components that has frequency 1 in a subarray of the given array.

Examples:

Enter: N = 3, arr[ ] = {2, 4, 2}
Output:  8
Rationalization: All potential subarrays are 
{2}: components with frequency one = 1.
{4}: components with frequency one = 1.
{2}: components with frequency one = 1.
{2, 4}: components with frequency one = 2.
{4, 2}: components with frequency one = 2.
{2, 4, 2}: components with frequency one = 1 (i.e., just for 4).
Whole rely of components = 1 + 1 + 1 + 2 + 2 + 1 = 8.

Enter: N = 2, arr[ ] = {1, 1}
Output: 2
Rationalization: All potential subarrays are 
{1}: components with frequency one = 1.
{1, 1}: components with frequency one = 0.
{1}: components with frequency one = 1.
Whole rely of components = 1 + 0 + 1 = 2.

Naive Strategy: The easy thought is to calculate all of the potential subarrays and for every subarray rely the variety of components that are current solely as soon as in that subarray and add that rely to the ultimate reply.

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

Environment friendly Strategy: For the above strategy, we are going to run out of time if the scale of the array may be very massive. Due to this fact we’ve to optimize it. We will effectively calculate the reply utilizing Hashing primarily based on the under thought:

Right here we are going to consider the contribution completed by every component to the ultimate rely. 

Say a component at index i has two different occurrences at j^th and ok^th index (j < i < ok). On this case, the component at i^th index has (i – j) * (ok – i) variety of selections to type a subarray the place it’s current solely as soon as.

Proof:

The i^th component can have (i – j) components from its left [including itself] in any of the subarray the place arr[i] has frequency 1.
Similary, it might have (ok – i) components from its proper [including itself] in any of the subarray satisfying the above situation.

So, from the essential precept of counting, we are able to see the entire variety of potential subarrays the place arr[i] has frequency 1 is (i – j) * (ok – i).

Comply with the steps talked about under to implement the thought:

• Initialize a map (say mp) to retailer the indices of occurrences of any component.
• Iterate by means of the array from i = 0 to N-1:
  • If arr[i] is arriving for the primary time then insert -1 first. (as a result of -1 will denote the primary incidence for ease of calculation)
  • Insert i in mp[arr[i]].
• Once more for ease of calculation insert N on the finish of every entry of the map.
• Now traverse by means of every component of the map and use the above system to calculate the contribution of the component current in every index.
• Return the ultimate rely because the required reply.

Beneath is the implementation of the above thought.

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