Raghav - 1 year ago 68

C++ Question

Is there any STL function in C++ that allows me to find all indices of duplicates in an array?

For eg:

`int array[] = {1,1,2,3,4};`

Should return 0,1

Answer Source

Assuming you cannot modify the array by sorting, efficiently, you could use a `std::unordered_set`

and `unordered_map`

. This does it in `O(N) + O(1) + O(1)`

:

```
template<typename Iter>
std::vector<int> duplicate_indices(Iter first, Iter last){
std::unordered_set<int> rtn;
std::unordered_map<int, int> dup;
std::size_t i = 0;
while(first != last){
auto iter = dup.find(*first);
if(iter != dup.end()){
rtn.insert(iter->second);
rtn.insert(i);
}
dup.insert(std::make_pair(*first, i));
++i;
++first;
}
return {rtn.begin(), rtn.end()};
}
```

Explanation:

Given an array `A`

- Using a set of unique indices,
`rtn`

. Using a

`KV`

map,`dup`

; where`k`

is an element in the array`A`

, and`v`

is the index of that element in the array.For Each item,

`a`

with index`i`

in the array, find`kv`

if the item exists as`k`

in`dup`

.- If it doesn't exist,
- Add
`i`

to`rtn`

- Add
`v`

to`rtn`

- Add
- Else, add
`a`

and`i`

as`kv`

into`dup`

- If it doesn't exist,
- return
`rtn`

See a full example live here.

For an input of:

```
int array[] = {1,1,2,3,4};
```

Outputs

```
1 0
```

Again,

For an input of:

```
int array[] = {1, 1, 2, 3, 4, 1, 0, 0, 9};
```

Outputs

```
7 0 5 1 6
```

If you need the indices in order, you could simply sort the resulting array.