Algo Breakdown — areThereDuplicates

Below I will share my process in solving a simple algorithmic programming challenge which has me create a function called ‘areThereDuplicates’. ‘areThereDuplicates’ should be able to take any number of arguments and find whether any of those arguments passed to it are duplicates. This might be a useful algorithm if, for instance, you are determining if a card in a card collection already exists.

Useful to breakdown, especially if you have a use case, to determine the exact nature of the problem.

The description wasn’t so complicated as to necessitate a list of objects as more convoluted problems tend to but I do it anyway because it is a good habit, helps communicate your intentions to others, and makes an easy to read list for yourself to quickly reference.

Here I’ll start by creating a standard arrow function, properly titled.

I set up by working my way down my list of objectives. Nothing’s too mundane, you’ll have to do it anyway.

Next, ‘areThereDuplicates’ will need to be able to take any number of arguments and there are really two ways to do this.

  1. You can access the arguments object with the function and not declare any parameters.

Here, I am leaning towards using the spread operator since it seems more explicit to me.

Careful kids, those args are explicit.

Now that we have the function framed out, we can start working on the inner logic. For this algorithm, I see two possible methods for solving our problem of finding duplicates in the arguments.

  1. We can use a two-pointer approach to iterate through the args array and return true if the right pointer value matches the left pointer value or false otherwise.

The two-pointer approach seems clunky here and I’d rather reduce my time iterating over an array as much as possible so I’ll be implementing the frequency counter approach.

First, we’ll create an empty object and then we’ll iterate through the args array initializing or incrementing values until we complete our run through the array. That one pass-through should be all that’s needed, reducing the complexity of our function. Let’s see what that looks like.

areThereDuplicates(‘a’, ‘b’, ‘c’, ‘a’) // -> { ‘a’: 2, ‘b’: 1, ‘c’: 1 } // might have been a better example here.

Then, as we can see, our ‘argFrequency’ object has a key for each unique value in our ‘args’ array. If there is already a value that has a key within our ‘argFrequency’ object, the value of that key is incremented by 1.

So finding out whether a value within the ‘args’ array is given more than once, or is a duplicate, should just be a matter of iterating through the key values of ‘argFrequency’ to test whether any of the values are greater than 1 and to return the appropriate boolean value.

Line 13. Initialize this key at 0 or add 1 to that key's value.

This solves our problem with O(n) complexity.

  • We create an array of arguments which we then convert to an object with our first loop to keep track of the frequency that values occur within that array we made.

For all intents and purposes, this solution shouldn’t have to be refactored, but it can be.

On my first solution, my ESLinter configuration flagged several of the techniques I used. I disabled them temporarily.

In ‘Eslinter is my JS Spirit Guide’ I mention how some rules are custom.

Here’s what happens when I re-enable them. Squiggle city.

MDN also mentions ‘for…in’ shouldn’t be used in cases where order matters.

Both errors thrown by my linter involve the ‘for…in’ looping and I don’t 100% grasp the comments so my first move is to check what MDN has to say about ‘for…in’ use cases.

“It may be most practically used for debugging purposes, being an easy way to check the properties of an object (by outputting to the console or otherwise).”

They go into a lot more detail before that so I recommend reading the entire page. I see this kind of iteration a lot and its usage might be worth a quick think.

Since I’m just iterating, I decide to turn the ‘for…in’ loops into ‘for’ loops to see if that makes the linter happy.

There is the question of how to iterate through the values of an object and I remembered one of the comments recommend simply using ‘Object.values’. This gives me an array containing the values of ‘argFrequency’.

How cool is that? -> Object.{keys, values, entries} -> Well I think it’s cool ok?

Now, while my refactored solution may be a little slower it keeps the same linear complexity. The added benefit to this solution is that it makes much more sense to me.

What input would break this?
  • We create an array ‘args’ from our arguments with the spread operator.

That’s all I have for this algorithm. I hope you learned something from reading my take on the different solutions. I know I learned a bit about ‘for…in’ and that sometimes, writing out a good ol’ ‘for loop’ is just the best way to go. Every object-oriented programmer in the universe will know what you’re doing and there is little to be disputed about the technique.

I think my sensibilities are moving towards creating simpler code (in that your code does exactly what you intend for it to, not that you are using a method for your purpose perhaps just because it reads better or takes up fewer lines).

I’ve thought in the past that refactors were supposed to be a flourish or reduce lines of code. Lately, my refactoring has been about simplifying my solutions by using lightweight methods that explicitly demonstrate the purpose of my code.

I’m curious to know where your heads are at with this philosophy. Do you strive for one-liners in your refactors, or to shave time off even if it makes your code more implicit? Leave a comment or message me on LinkedIn if you wanna talk about it. I’m always down to hear new ideas and learn new things.

Frontend Software Developer and Security Technician with experience in Ruby, Rails, JavaScript, and React. Flatiron Software Engineering Alumni.