## Thursday, May 26, 2016

### 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;`
`}`