# Finding duplicates in an array and its index number

**URL:** <https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307>\
**Category:** ruby-talk\
**Created:** [19 April 2012 21:53 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307 "2012-04-19T21:53:25Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [19 April 2012 21:53 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/1 "2012-04-19T21:53:25Z")

</div>

Hi,

I have following array and I am trying to find if there are duplicates  
in the array. I also want to find out their index.

e.g.

a=[1,2,3,1,3]

Here 1 is a duplicate which comes twice and its index is 0 and 3 in the  
array.

Any suggestions?

Thanks

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

---

<div class="post-metadata">

**Author:** ![Jeff\_Lunt](https://avatars.discourse-cdn.com/v4/letter/j/7ea924/32.png) [@Jeff\_Lunt](https://rubytalk.org/u/Jeff_Lunt)\
**Post date:** [19 April 2012 22:06 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/2 "2012-04-19T22:06:37Z")

</div>

I'm curious what the purpose is. If it's simply to remove the duplicates  
you can call .uniq on the array to remove duplicates.

> **···**
>
> On Apr 19, 2012 4:55 PM, "newto ruby" \<lists@ruby-forum.com\> wrote:
> 
> > Hi,
> > 
> > I have following array and I am trying to find if there are duplicates  
> > in the array. I also want to find out their index.
> > 
> > e.g.
> > 
> > a=[1,2,3,1,3]
> > 
> > Here 1 is a duplicate which comes twice and its index is 0 and 3 in the  
> > array.
> > 
> > Any suggestions?
> > 
> > Thanks
> > 
> > --  
> > Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [19 April 2012 22:49 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/3 "2012-04-19T22:49:49Z")

</div>

Hi,

As always, there are many ways to do this.

A highlevel approach: (short but not really inefficient)

> **···**
>
> ####  
> x = [1, 2, 3, 2, 4, 5, 4, 4]
> 
> a = x.each\_with\_index.group\_by(&:first).inject({}) do |result, (val,  
> group)|  
> &nbsp;&nbsp;next result if group.length == 1  
> &nbsp;&nbsp;result.merge val =\> group.map {|pair| pair[1]}  
> end
> 
> p a  
> ####
> 
> A more efficient lowlevel solution would be to iterate over the array,  
> compare the values and save the indices in case of duplicates.
> 
> --  
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

---

<div class="post-metadata">

**Author:** ![Sam\_Duncan](https://avatars.discourse-cdn.com/v4/letter/s/b9bd4f/32.png) [@Sam\_Duncan](https://rubytalk.org/u/Sam_Duncan)\
**Post date:** [19 April 2012 22:58 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/4 "2012-04-19T22:58:26Z")

</div>

How about;

1.9.3p125 :001 \> foo = [1,2,3,1,3]  
&nbsp;&nbsp;=\> [1, 2, 3, 1, 3]  
1.9.3p125 :002 \> dup\_indices = Hash.new {|h,k| h[k]=}  
&nbsp;&nbsp;=\> {}  
1.9.3p125 :003 \> foo.each\_index {|i| dup\_indices[foo[i]] \<\< i unless 1 == foo.count(foo[i])}  
&nbsp;&nbsp;=\> [1, 2, 3, 1, 3]  
1.9.3p125 :004 \> dup\_indices  
&nbsp;&nbsp;=\> {1=\>[0, 3], 3=\>[2, 4]}

Sam

> **···**
>
> On 20/04/12 09:53, newto ruby wrote:
> 
> > Hi,
> > 
> > I have following array and I am trying to find if there are duplicates  
> > in the array. I also want to find out their index.
> > 
> > e.g.
> > 
> > a=[1,2,3,1,3]
> > 
> > Here 1 is a duplicate which comes twice and its index is 0 and 3 in the  
> > array.
> > 
> > Any suggestions?
> > 
> > Thanks

---

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [20 April 2012 10:34 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/5 "2012-04-20T10:34:04Z")

</div>

I do a lot of indexing of data. Usually they're multi-field records, and  
each data set will have multiple indexes. The technique I use is below.  
This indexes all elements of the array. So, then to find duplicates, you  
have to loop again to find array counts \> 1. Anyway, it's a slightly  
different way to do it in the event an index of all entries would be  
useful for lookups.

data = [1, 2, 3, 1, 3, 4, 6, 5, 4]  
dataIndex = {}

data.each\_with\_index do |value, indx|

&nbsp;&nbsp;index\_key = value  
&nbsp;&nbsp;index\_value = indx

&nbsp;&nbsp;if !dataIndex.has\_key?(index\_key)  
&nbsp;&nbsp;&nbsp;&nbsp;dataIndex.store(index\_key, [])  
&nbsp;&nbsp;end

&nbsp;&nbsp;dataIndex[index\_key].push(index\_value)  
end

p dataIndex

dataIndex.each do |key, indxs|  
&nbsp;&nbsp;if indxs.count \> 1  
&nbsp;&nbsp;&nbsp;&nbsp;# do something  
&nbsp;&nbsp;&nbsp;&nbsp;puts "#{key} appears at #{indxs.join(', ')}"  
&nbsp;&nbsp;end  
end

-- gw

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

---

<div class="post-metadata">

**Author:** ![Lars\_Haugseth1](https://avatars.discourse-cdn.com/v4/letter/l/839c29/32.png) [@Lars\_Haugseth1](https://rubytalk.org/u/Lars_Haugseth1)\
**Post date:** [20 April 2012 10:46 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/6 "2012-04-20T10:46:07Z")

</div>

Generate a hash with unique items as keys, and arrays of indices as values,  
then select only those with more than one index:

array = [1, 2, 3, 4, 5, 3, 6, 7, 2, 8, 1, 9]

array.each\_with\_index.reduce({}) { |hash, (item, index)|  
&nbsp;&nbsp;&nbsp;hash[item] = (hash[item] || ) \<\< index  
&nbsp;&nbsp;&nbsp;hash  
}.select { |key, value|  
&nbsp;&nbsp;&nbsp;value.size \> 1  
}

# =\> {1=\>[0, 10], 2=\>[1, 8], 3=\>[2, 5]}

> **···**
>
> On 04/19/2012 11:53 PM, newto ruby wrote:
> 
> > Hi, I have following array and I am trying to find if there are duplicates in the array. I also want to find out their index.
> 
> --  
> Lars Haugseth

---

<div class="post-metadata">

**Author:** ![Jeff\_Lunt](https://avatars.discourse-cdn.com/v4/letter/j/7ea924/32.png) [@Jeff\_Lunt](https://rubytalk.org/u/Jeff_Lunt)\
**Post date:** [19 April 2012 22:08 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/7 "2012-04-19T22:08:12Z")

</div>

If you really want to know how it finds the duplicates, look at the source  
code for the .uniq method as a starting point.

> **···**
>
> On Apr 19, 2012 5:06 PM, "Jeff Lunt" \<jefflunt@gmail.com\> wrote:
> 
> > I'm curious what the purpose is. If it's simply to remove the duplicates  
> > you can call .uniq on the array to remove duplicates.  
> > On Apr 19, 2012 4:55 PM, "newto ruby" \<lists@ruby-forum.com\> wrote:
> > 
> > > Hi,
> > > 
> > > I have following array and I am trying to find if there are duplicates  
> > > in the array. I also want to find out their index.
> > > 
> > > e.g.
> > > 
> > > a=[1,2,3,1,3]
> > > 
> > > Here 1 is a duplicate which comes twice and its index is 0 and 3 in the  
> > > array.
> > > 
> > > Any suggestions?
> > > 
> > > Thanks
> > > 
> > > --  
> > > Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [19 April 2012 23:03 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/8 "2012-04-19T23:03:36Z")

</div>

Jan E. wrote in post #1057484:

> A more efficient lowlevel solution would be to iterate over the array,  
> compare the values and save the indices in case of duplicates.

... like this:

> **···**
>
> ####  
> x = [1, 2, 3, 2, 4, 5, 4, 4]
> 
> duplicates = {}  
> x.each\_with\_index do |value, i|  
> &nbsp;&nbsp;(i + 1).upto x.length - 1 do |j|  
> &nbsp;&nbsp;&nbsp;&nbsp;if x[j] == value  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;duplicates[value] = [i] if duplicates[value].nil?  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;duplicates[value] \<\< j  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;end  
> end
> 
> p duplicates  
> ####
> 
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [20 April 2012 16:55 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/9 "2012-04-20T16:55:36Z")

</div>

Greg Willits wrote in post #1057552:

> I do a lot of indexing of data. Usually they're multi-field records, and  
> each data set will have multiple indexes. The technique I use is below.  
> This indexes all elements of the array. So, then to find duplicates, you  
> have to loop again to find array counts \> 1. Anyway, it's a slightly  
> different way to do it in the event an index of all entries would be  
> useful for lookups.

DOH. That first loop only needed to be:

data.each\_with\_index do |value, indx|  
&nbsp;&nbsp;&nbsp;if !dataIndex.has\_key?(key)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dataIndex.store(key, )  
&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;dataIndex[key].push(value)  
end

That's what I get for doing a quick transcribe of project code.

-- gw

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Ryan\_Davis1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/ryan_davis1/32/1848_2.png) [@Ryan\_Davis1](https://rubytalk.org/u/Ryan_Davis1)\
**Post date:** [20 April 2012 23:47 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/10 "2012-04-20T23:47:41Z")

</div>

Don't use reduce/inject for non-reductive applications. Use something more appropriate, like a plain each.

Also use Hash to its full capabilities:

hash = Hash.new { |h,k| h[k] = }

then it is as clean as:

array.each\_with\_index do |val, idx|  
&nbsp;&nbsp;hash[val] \<\< idx  
end

Notice how you're not constantly re-assigning hash for no good reason in my version? That adds up, but more importantly it obfuscates the original intent.

> **···**
>
> On Apr 20, 2012, at 03:46 , Lars Haugseth wrote:
> 
> > On 04/19/2012 11:53 PM, newto ruby wrote:
> > 
> > > Hi, I have following array and I am trying to find if there are duplicates in the array. I also want to find out their index.
> > 
> > Generate a hash with unique items as keys, and arrays of indices as values,  
> > then select only those with more than one index:
> > 
> > array = [1, 2, 3, 4, 5, 3, 6, 7, 2, 8, 1, 9]
> > 
> > array.each\_with\_index.reduce({}) { |hash, (item, index)|  
> > hash[item] = (hash[item] || ) \<\< index  
> > hash  
> > }.select { |key, value|  
> > value.size \> 1  
> > }
> > 
> > # =\> {1=\>[0, 10], 2=\>[1, 8], 3=\>[2, 5]}

---

<div class="post-metadata">

**Author:** ![Robert\_K1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/robert_k1/32/1830_2.png) [@Robert\_K1](https://rubytalk.org/u/Robert_K1)\
**Post date:** [22 April 2012 11:46 UTC](https://rubytalk.org/t/finding-duplicates-in-an-array-and-its-index-number/65307/11 "2012-04-22T11:46:16Z")

</div>

OK folks,

news from the service department. Here's the shootout:

> <https://gist.github.com/rklemme/2463600>

Turns out quickest is one of the less arcane solutions:

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dups = {}

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dat.each\_with\_index do |val, idx|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(dups[val] ||= []) \<\< idx  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dups.delete\_if {|k,v| v.size == 1}

A few remarks:

It's amazing how many forms even the same algorithm can take in Ruby.  
Just the different options for adding to a Hash (#default\_proc,  
#fetch, ||=) can make a huge visual difference although the underlying  
strategy of all these algorithms is the same.

Downside of Jan's first approach is that it has effort O(n\*\*2) in  
terms of elements in the array because of the nested iteration. Sam's  
approach has a similar quality although less obvious (it's in the  
#count).

Allocating multiple Hash instances is what makes Jan's second approach slow.

As always, #inject (or #reduce) approaches are slower than others.

The best strategy is to create a Hash with elements as keys and Arrays  
of indexes as values. This approach won't suffer for large inputs  
from the O(n\*\*2) issue.

For one off scripts and infrequent execution it doesn't really matter much. 🙂

Kind regards

robert

> **···**
>
> --  
> remember.guy do |as, often| as.you\_can - without end  
> [http://blog.rubybestpractices.com/](http://blog.rubybestpractices.com/)