Summary

Build out a method for finding the first duplicate element from an array.

Exercise Description

"Define a method that will return the first repeated element from an array."

Example Data

arr_one = [5, 3, 4, 5, 3, 1]
first_repeated_element(arr_one)
=> 5

arr_two = [3, 5, 3, 4, 5, 3, 1]
first_repeated_element(arr_two)
=> 5

Real World Usage

This exercise will help you prevent from using duplicate info within your code base.

Test Cases

Code File

Solution Walk Through

In this Ruby programming exercise, we're going to have some fun because we're going to figure out how we can find the first repeated element in a ruby array and we're going to learn quite a bit about the hash data structure as we do it.

So coming down to the test,

let's walk through what our method needs to be able to behave like. And so the first thing is that it needs to return the first repeated element from an array. So right here we have a sample array and it has the elements of 5, 3, 4, 5, 3, and 1. Now the behavior we're looking for is to return the Integer 5 in this case, because as you can see we have a 5 as the first element and then as the 4th element. The 3 also is a duplicate but it's not repeated until after the 5.

Moving down to the second example, right here we have another array that has multiple duplicates we have 3 3's and then we have two 5s. But as you can see the very first element and then the third element are both 3. And so in this case the method should return the integer 3. There are also a couple nil guards here. So if the array is completely empty then our method should simply return nil and if there are no duplicates at all found then it should also return nil.

As a caveat, if you are looking to take this code and place it into a production application you will have to check and see if there are duplicates or if the array is empty or else you could run into an error and so that's something to keep in mind. In a real-world scenario what I'd most likely do is build out a module or a class that performs this kind of check and it did it internally. There is a kind of a precedent in some of the coding exercises I've seen in other programming languages where whenever this is the case they return negative one.

However, I didn't really want to use that for this implementation because what if we had an array that contained a set of duplicate negative ones I think that would lead to some confusing behavior. So now with all that being said let's actually build the implementation.

So the very first thing I'm gonna do is take care of the second spec and so I am going to return nil if the array is empty. So on one line, I can take care of the spec there on line 16 that says returns nil for an empty array. Now the way that I'm going to build out this behavior is I'm going to create what is called a counter hash and so what that allows us to do is to create a hash data structure that keeps track of our values and so I can create a counter hash by saying counter underscore hash equals hash dot new and then I'm going to pass in a default of 0.

counter_hash = Hash.new(0)

Now let's see exactly what this means and this is one of the key elements I want you to take away from this solution because there are a number of ways to build out this first repeated element algorithm. But I specifically wanted to walk through an interesting caveat when it comes to working with hashes in Ruby and so if I create a couple hashes in ruby I'm going to say hash_one = hash.new so notice I'm not passing on any values to new.

Then if I create another hash called hash_two and I use the exact same syntax that I'm using on our file in line 6 you can see that the return value here is completely identical

and so you may think that it is unnecessary to pass in any value there. However what Ruby allows us to do when you pass in a default argument into the hash constructor is it allows you to do what we're looking to do which is to create a counter and so if I want to do something like this where I want to add on to the hash so I'm gonna say hash_one and just say something for the key it doesn't really matter but notice because we have an empty hash. There is a new key called something and so if I try to perform a task like this where I say hash_one something and then I try to create an incrementer. So I say I want you to whatever your original value as I want to increment that by 1 and this is how we're going to build our own counter so this is very key.

If I run this you'll see that I get an error.

It says undefined method + for nil class and that makes sense because as you could see we did not have any keys in our hash.

Now if I change to this and I try to perform the same exact behavior for hash_two the one where we set the value and set that default. Now notice this works perfectly fine

and so our counter works every time this runs it is incrementing the value.

But if we look at hash_one you can see it's empty, hash_two now has a key that says something and then a counter that has now counted up to 5.

And so this is a type of behavior that we want and if we did not pass in a default value into our hash constructor then it would not work. So this is very key to have this hash code here and now that that's in place now we want to iterate over the array. So I'm gonna say array.each do and I'm just going to use e for element for the block variable and now I can call the counter hash so I'm gonna say counter hash pass in e as the key and then we're going to increment. So I'm going to say counter hash e plus equals so increment by 1.

arr.each do |e|
  counter_hash[e] = counter_hash[e] += 1
end

If you notice this code is pretty much identical to what we just tested out in the irb session where we have a hash and we're trying to increment but we have to accommodate for the situation where each one of these values is going to be set to empty.

So we're going to have no keys in our hash when this starts and we need to be able to increment it. And what this part of the application is going to do is it's going to iterate over each element. When it finds a duplicate it is going to set it and then it's going to increment the counter. And so in this case as it goes through this array the first time it goes through it's going to set the first key to 5. Then it's going to go through to the second element and it's going to create a key called 3. Now 5 is going to have a value of 1, 3 is going to have a value of 1, then 4 is going to be created.

So we're going to have three elements in the hash and that's going to have a value of 1. Then when it gets to 5 it is going to go in it's going to say OK we already have a key for 5 and now it's going to try to increment it and it's going to no longer be one it's now going to be two and that is all our program needs to know that we have hit our first duplicate and it should return and so the next item that we need to add is a return statement.

So I'm going to say I want to return the element, so in that first example, that would return 5 and I want to return it if the counter hash for that value is greater than 1. So let me save this and I'm going to grab this first array here just so we can test this out. So now if I try to run this I'll say first_repeated_element pass in arr_one and now let's test this out by just printing it out into the terminal.

So I'm just going to say put's and now if I run this code.

ruby may/21_spec.rb

You can see that prints out 5. So that is working properly.

Now let's test our specs and see which ones are still passing and which ones are failing. So if I run this you can see that it looks like we're on the right track. We have two of our specs passing and only one failure.

So the only one that we have left is where it says first repeated element returns nil if no duplicates are found. So in order to take care of that situation, I'm gonna say return nil at the very end. So on line 8 if no duplicates are found at all in the entire system then it is never going to hit line 11. So it's never going to return the element and in that case, at the very end of the entire method, it's simply going to return nil.

If I save this and run it you can see we have 3 examples no failures

and so we have successfully created a method that finds the first repeated element in an array and we also learned a few new tips and tricks for working with Ruby hashes.