# Number of sub-arrays that have at least one duplicate

Given an array *arr* of n elements, the task is to find the number of the sub-arrays of the given array that contain at least one duplicate element.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {1, 2, 3}Output:0

There is no sub-array with duplicate elements.Input:arr[] = {4, 3, 4, 3}Output:3

Possible sub-arrays are {4, 3, 4}, {4, 3, 4, 3} and {3, 4, 3}

**Approach:**

- First, find the total number of sub-arrays that can be formed from the array and denote this by
*total*then*total = (n*(n+1))/2*. - Now find the sub-arrays that have all the elements distinct (can be found out using window sliding technique) and denote this by
*unique*. - Finally, the number of sub-arrays that have at least one element duplicate are
*(total – unique)*

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `#define ll long long int` `using` `namespace` `std;` `// Function to return the count of the` `// sub-arrays that have at least one duplicate` `ll count(ll arr[], ll n)` `{` ` ` `ll unique = 0;` ` ` `// two pointers` ` ` `ll i = -1, j = 0;` ` ` `// to store frequencies of the numbers` ` ` `unordered_map<ll, ll> freq;` ` ` `for` `(j = 0; j < n; j++) {` ` ` `freq[arr[j]]++;` ` ` `// number is not distinct` ` ` `if` `(freq[arr[j]] >= 2) {` ` ` `i++;` ` ` `while` `(arr[i] != arr[j]) {` ` ` `freq[arr[i]]--;` ` ` `i++;` ` ` `}` ` ` `freq[arr[i]]--;` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `else` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `ll total = n * (n + 1) / 2;` ` ` `return` `total - unique;` `}` `// Driver code` `int` `main()` `{` ` ` `ll arr[] = { 4, 3, 4, 3 };` ` ` `ll n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << count(arr, n) << endl;` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `import` `java.util.*;` `class` `GFG` `{` `// Function to return the count of the` `// sub-arrays that have at least one duplicate` `static` `Integer count(Integer arr[], Integer n)` `{` ` ` `Integer unique = ` `0` `;` ` ` `// two pointers` ` ` `Integer i = -` `1` `, j = ` `0` `;` ` ` `// to store frequencies of the numbers` ` ` `Map<Integer, Integer> freq = ` `new` `HashMap<>();` ` ` `for` `(j = ` `0` `; j < n; j++)` ` ` `{` ` ` `if` `(freq.containsKey(arr[j]))` ` ` `{` ` ` `freq.put(arr[j], freq.get(arr[j]) + ` `1` `);` ` ` `}` ` ` `else` ` ` `{` ` ` `freq.put(arr[j], ` `1` `);` ` ` `}` ` ` `// number is not distinct` ` ` `if` `(freq.get(arr[j]) >= ` `2` `)` ` ` `{` ` ` `i++;` ` ` `while` `(arr[i] != arr[j])` ` ` `{` ` ` `freq.put(arr[i], freq.get(arr[i]) - ` `1` `);` ` ` `i++;` ` ` `}` ` ` `freq.put(arr[i], freq.get(arr[i]) - ` `1` `);` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `else` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `Integer total = n * (n + ` `1` `) / ` `2` `;` ` ` `return` `total - unique;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `Integer arr[] = { ` `4` `, ` `3` `, ` `4` `, ` `3` `};` ` ` `Integer n = arr.length;` ` ` `System.out.println(count(arr, n));` `}` `}` `// This code is contributed by 29AjayKumar` |

## Python3

`# Python3 implementation of the approach` `from` `collections ` `import` `defaultdict` `# Function to return the count of the` `# sub-arrays that have at least one duplicate` `def` `count(arr, n):` ` ` `unique ` `=` `0` ` ` `# two pointers` ` ` `i, j ` `=` `-` `1` `, ` `0` ` ` `# to store frequencies of the numbers` ` ` `freq ` `=` `defaultdict(` `lambda` `:` `0` `)` ` ` `for` `j ` `in` `range` `(` `0` `, n):` ` ` `freq[arr[j]] ` `+` `=` `1` ` ` `# number is not distinct` ` ` `if` `freq[arr[j]] >` `=` `2` `:` ` ` `i ` `+` `=` `1` ` ` ` ` `while` `arr[i] !` `=` `arr[j]:` ` ` `freq[arr[i]] ` `-` `=` `1` ` ` `i ` `+` `=` `1` ` ` ` ` `freq[arr[i]] ` `-` `=` `1` ` ` `unique ` `=` `unique ` `+` `(j ` `-` `i)` ` ` ` ` `else` `:` ` ` `unique ` `=` `unique ` `+` `(j ` `-` `i)` ` ` ` ` `total ` `=` `(n ` `*` `(n ` `+` `1` `)) ` `/` `/` `2` ` ` `return` `total ` `-` `unique` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `arr ` `=` `[` `4` `, ` `3` `, ` `4` `, ` `3` `]` ` ` `n ` `=` `len` `(arr)` ` ` `print` `(count(arr, n))` `# This code is contributed` `# by Rituraj Jain` |

## C#

`// C# implementation of the approach` `using` `System;` `using` `System.Collections.Generic; ` `class` `GFG` `{` `// Function to return the count of the` `// sub-arrays that have at least one duplicate` `static` `int` `count(` `int` `[]arr, ` `int` `n)` `{` ` ` `int` `unique = 0;` ` ` `// two pointers` ` ` `int` `i = -1, j = 0;` ` ` `// to store frequencies of the numbers` ` ` `Dictionary<` `int` `,` ` ` `int` `> freq = ` `new` `Dictionary<` `int` `,` ` ` `int` `>();` ` ` `for` `(j = 0; j < n; j++)` ` ` `{` ` ` `if` `(freq.ContainsKey(arr[j]))` ` ` `{` ` ` `freq[arr[j]] = freq[arr[j]] + 1;` ` ` `}` ` ` `else` ` ` `{` ` ` `freq.Add(arr[j], 1);` ` ` `}` ` ` `// number is not distinct` ` ` `if` `(freq[arr[j]] >= 2)` ` ` `{` ` ` `i++;` ` ` `while` `(arr[i] != arr[j])` ` ` `{` ` ` `freq[arr[i]] = freq[arr[i]] - 1;` ` ` `i++;` ` ` `}` ` ` `freq[arr[i]] = freq[arr[i]] - 1;` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `else` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `int` `total = n * (n + 1) / 2;` ` ` `return` `total - unique;` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `[]arr = { 4, 3, 4, 3 };` ` ` `int` `n = arr.Length;` ` ` `Console.WriteLine(count(arr, n));` `}` `}` `// This code is contributed by PrinciRaj1992` |

## Javascript

`<script>` `// Javascript implementation of the approach` `// Function to return the count of the` `// sub-arrays that have at least one duplicate` `function` `count(arr, n)` `{` ` ` `let unique = 0;` ` ` `// two pointers` ` ` `let i = -1, j = 0;` ` ` `// to store frequencies of the numbers` ` ` `let freq = ` `new` `Map();` ` ` `for` `(j = 0; j < n; j++) {` ` ` `if` `(freq.has(arr[j])){` ` ` `freq.set(arr[j], freq.get(arr[j]) + 1)` ` ` `}` `else` `{` ` ` `freq.set(arr[j], 1)` ` ` `}` ` ` `// number is not distinct` ` ` `if` `(freq.get(arr[j]) >= 2) {` ` ` `i++;` ` ` `while` `(arr[i] != arr[j]) {` ` ` `freq.set(arr[i], freq.get(arr[i]) - 1)` ` ` `i++;` ` ` `}` ` ` `freq.set(arr[i], freq.get(arr[i]) - 1)` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `else` ` ` `unique = unique + (j - i);` ` ` `}` ` ` `let total = n *(n + 1) / 2;` ` ` `return` `total - unique;` `}` `// Driver code` ` ` `let arr = [ 4, 3, 4, 3 ];` ` ` `let n = arr.length;` ` ` `document.write(count(arr, n) + ` `"<br>"` `);` `// This code is contributed by _saurabh_jaiswal` `</script>` |

**Output:**

3

**Time Complexity:** O(N)

**Auxiliary Space:** O(N)