Problem-Solving in Vanilla JS đź’«
Detecting the Only Duplicate in a List
As a recent bootcamp grad, I spend a large chunk of my time aspiring to be more productive than I actually am. Every morning, I wake up with delusions of grandeur, “Today’s the day! I’ll be super productive! Apply to jobs, network a bunch, work on my portfolio, learn redux, attend those MeetUps…” You get the picture.
I fall short most of the time, but one thing I’ve remained consistent with is algorithm practice. I still have much to learn but I quite enjoy them! Most of the time, I start out a problem without the faintest clue about what I’m working with or where this journey will take me. Sounds daunting but the more you practice, the more exciting it becomes. I delight in hunting down patterns and making sense of all things nebulous. So if you’re intimidated by algorithms, you’re in the right place. I’m scared of everything so I’ll guide you gently! I’ve always enjoyed breaking down concepts to make them more palatable, and have heard it’s best practice to walk through code as if you’re explaining it to someone who has no idea what it does. So to quote my parce*, J. Balvin, “Leggo”.
Problem: Given a list nums of length n + 1 picked from the range 1, 2, ..., n. By the pigeonhole principle, there must be a duplicate. Find and return it. There is guaranteed to be exactly one duplicate.
Step 1: What is this asking me to do? When starting a problem, my first objective is always to determine exactly what is being asked of me. In this case, I have a list of numbers and am finding the single duplicate (if it exists — don’t forget your edge cases!) and returning it.
Step 2: Pseudocode. Now that you know what needs to be done, what’s your game plan? Here’s where I’ll usually analyze the examples provided in order to find any discernible patterns that will help me get to a solution.
Once I spot something I can work with, I begin to set up my code.
- Since I’m working with an array, nums, I’ll need to iterate through it to capture each element. As I’m iterating through, I’ll need to keep track of which elements already exist in the array. This way, the moment I reach the duplicate (there can only be one), I can return it.
- In order to keep track of each value in the array, I’ll set up an empty object. As I iterate through the array, I want to assign each element as a key in the array with a value of 1. This will serve as my counter.
Step 3: Bring it to life. According to my pseudocode, I need to create an empty object to hold and track my values before iterating through the array. So that’s the first line I’ll write. Next, I want to iterate through this array. We want to grab the value of each element in the array, so a simple for loop will suffice.
I personally like to assign each array element to a variable so that I can reference it later. You can skip this step if you don’t want any extra variables, though. Now we can implement our conditional logic: if obj[element] === undefined, I want to create a new key-value pair inside the object. This is how we will keep track of existing elements so that we can check for duplicates.
Object[key] will always render a value, therefore if it does not exist, it will return undefined. Since our object is empty, we know it will return undefined. So we’ll go ahead and update the object by adding a key (element) with a value of 1, since the element has appeared in the array.
Let’s say the array we’re working with is [1, 9, 8, 1] and we are on the third iteration of the loop, our object will look like:
Since we know we will reach our duplicate value in the next iteration, we need to account for that in our code. At the moment, our for loop is assigning new key-value pairs to the object if the key does not exist in the object.
If the key exists in the array, (obj[1] = 1 and is therefore not undefined) we will simply return the element and exit the loop!
In this case, returning inside of the loop is acceptable since our objective is to return the duplicate value. However, in other cases, you will want to loop through the entire array, in which case you would return outside the loop.
This is an easy problem but powering through algorithms and emerging victorious leaves me with a feeling akin to when I find out Bad Bunny just blessed us with some more sadboi bangers. ✨ Euphoric ✨
*Parce is Colombian slang for a fellow Colombian. If you’ve been binge-watching Narcos but don’t know this you’re slackin’.
