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.
2. You can use the spread operator and the name of the parameter to put any arguments passed to the function within an array you can access with the parameter name.

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.
2. We can use a frequency counter approach and iterate through the args array creating a key for each value if no key already exists or increment the value of that key’s value if it does. Then we can access the values of the object returning true if any value is greater than 1 or false if none are.

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.
• An object is also preferred because that means we won’t have to iterate across the array again which reduces our complexity.
• Then our second loop iterates across the object ‘argFrequency’ to evaluate whether the value of each key is greater than 1.

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.
• We iterate through ‘args’ to create the object ‘argFrequency’ with keys representing each unique value of ‘args’ and the value for those keys which represent the number of times that value occurred within ‘args’.
• We do this by initializing a new key in ‘argFrequency’ for each value of ‘args’ if that key does not already exist, or incrementing the value for that key by 1if it does.
• Then we create an array ‘argFrequencyVals’ from the values of ‘argFrequency’.
• With our second loop, we iterate over ‘argFrequencyVals’, and on each index, we check if the value is greater than 1.
• If it is, we return true.
• If none of the values in ‘argFrequencyVals’ are greater than 1, the loop finishes, and the function ends by returning false.

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.