Count pairs formed by distinct element sub-arrays - GeeksforGeeks

Count pairs formed by distinct element sub-arrays - GeeksforGeeks
Given an array, count number of pairs that can be formed from all possible contiguous sub-arrays containing distinct numbers. The array contains positive numbers between 0 to n-1 where n is the size of the array.

int countPairs(int arr[], int n)

{

    // initialize number of pairs to zero

    int count = 0;

 

    //Left and right indexes of current window

    int right = 0, left = 0;

 

    // Boolean array visited to mark elements in

    // current window. Initialized as false

    vector<bool> visited(n, false);

 

    // While right boundary of current window

    // doesn't cross right end

    while (right < n)

    {

        // If current window contains all distinct

        // elements, widen the window toward right

        while (right < n && !visited[arr[right]])

        {

            count += (right - left);

            visited[arr[right]] = true;

            right++;

        }

 

        // If duplicate is found in current window,

        // then reduce the window from left

        while (left < right && (right != n &&

               visited[arr[right]]))

        {

            visited[arr[left]] = false;

            left++;

        }

    }

 

    return count;

}

Read full article from Count pairs formed by distinct element sub-arrays - GeeksforGeeks