Subarrays with distinct elements - GeeksforGeeks

Subarrays with distinct elements - GeeksforGeeks
Given an array, the task is to calculate the sum of lengths of contiguous subarrays having all elements distinct.

A simple solution is to consider all subarrays and for every subarray check if it has distinct elements or not using hashing. And add lengths of all subarrays having distinct elements. If we use hashing to find distinct elements, then this approach takes O(n2) time

An efficient solution is based on the fact that if we know all elements in a subarray arr[i..j] are distinct, sum of all lengths of distinct element subarrays in this sub array is ((j-i+1)*(j-i+2))/2. How? the possible lengths of subarrays are 1, 2, 3,……, j – i +1. So, the sum will be ((j – i +1)*(j – i +2))/2.

We first find largest subarray (with distinct elements) starting from first element. We count sum of lengths in this subarray using above formula. For finding next subarray of the distinct element, we increment starting point, i and ending point, j unless (i+1, j) are distinct. If not possible, then we increment i again and move forward the same way.

Time Complexity of this solution is O(n). Note that the inner loop runs n times in total as j goes from 0 to n across all outer loops. So we do O(2n) operations which is same as O(n).

int sumoflength(int arr[], int n)

{

    // For maintaining distinct elements.

    unordered_set<int> s;

 

    // Initialize ending point and result

    int j = 0, ans = 0;

 

    // Fix starting point

    for (int i=0; i<n; i++)

    {

        // Find ending point for current subarray with

        // distinct elements.

        while (j < n && s.find(arr[j]) == s.end())

        {

            s.insert(arr[j]);

            j++;

        }

 

        // Calculating and adding all possible length

        // subarrays in arr[i..j]

        ans += ((j - i) * (j - i + 1))/2;

 

        // Remove arr[i] as we pick new stating point

        // from next

        s.erase(arr[i]);

    }

 

    return ans;

}

Read full article from Subarrays with distinct elements - GeeksforGeeks