CheckiO Challenge 01: Non-unique Elements
In this challenge, you are given an array of integers, and your goal is to return an array containing only the non-unique elements from the given array. When I first attempted this, I made a common mistake, I didn’t thoroughly read the challenge statement. I immediately dove in and returned an array of all the elements that repeated, but only one instance of each element.
This challenge doesn’t want you to return a list of the elements that appear more than once. It wants you to remove the elements that only appear once.
Given: [1,2,3,1,3], your function should return [1,3,1,3] not [1,3] as I first thought. That being said. Let’s dig in. Here’s my solution on GitHub. Note that I am aware this is not an elegant solution, but it is my solution.
First, we initialize two empty arrays, retval and checked, to be used inside the loop. retval is the array that we will return once our function has fulfilled its duties. Inside the for loop, we will push elements that pass our test into this array. checked is an array to keep track of what elements we have already checked. At the end of each iteration of the for loop, we add the current element of the array we are looping through to checked. We need this array for the if() statement inside the for loop.
As these stories are being written for myself and people whose expertise lies at least somewhat beyond JavaScript 101, I will assume the reader is aware of what a for loop is. If not, check out the docs. Yes, I could have used forEach but I am more familiar with the for and thought that since this was the first challenge, I’d use the most simple version of the looping structure.
The checked array is easily the least elegant bit in this solution. We have to take up memory storing an entire unnecessary array. That array has to be both iterated through and updated during every pass through the array. This is a lot of overhead. If we were to input an array with tens of thousands of elements, by the time we had checked most of the values, we would effectively be handling three arrays with thousands of elements. Not ideal!
Inside the Loop
Each element in the given array, data, will be ran through the includes() method either once or twice. This method will be called once if the current element is in the checked array. If the element is not in that array, includes() will be called again on a sliced version of the original data array.
The nature of the ‘OR’ operator ( || ) is to stop its parent conditional statement’s processing if the first comparison returns true. This is why I chose the placement of the second comparison.
This is the one bit of optimization in my otherwise clunky algorithm.
Not only is the data.slice() array likely to be larger than the checked array, it is being recreated each time it is compared against. This is also why I placed it as the second condition in the if statement and didn’t assign it to a variable before the if statement. There will eventually be cases where the current element is already in the checked array. When that happens, there is no need to see if it is in the set of elements that occur after it, so why both creating a new array and calling includes() on it?
Slice what?
We are calling the slice() method on the input array starting on the element after the current element. Slice returns a copy of the array being sliced but only the elements after where you tell it to start. Hence the “(ii + 1)”. We don’t want to slice on the current element, because that includes() call would always return true. For instance, if we sliced [2,4,6,8,10] on the element at index 2, the number 6, we would be returned an array of [6,8,10]. If we then tested to see if that same element at index 2 in the first array was in the new array, it would always return “true”. Instead, we slice on the element following our current element, which in this example would return [8,10].
Push it
All that is left to do is call two push methods. One will (most likely) only be called sometimes, the other will always happen right before the end of each iteration.
If the current element is included in one of the two arrays in question, we push() it to the end of the retval array, the array we will be sending back to the calling function. Basically, retval is our “answer”. If the given array contains any unique elements, this method will only be called sometimes. If all of the elements in the given array occur more than once, this method will be called during each pass through the loop.
The second push() invocation takes place regardless of whether or not the current element passed our comparison tests. Remember, this array is a storehouse for all the elements we have already checked. If an element is in this array, there is no need to slice the input array and check the remaining elements. Therefore, we must add every element we check to this checked array.
Send it On Home
This will be the first and last time I explain a return statement. At any time during the operation of a function, if you have done everything you need to do, you can return information to the calling function, or store it in a variable.
You can have multiple return statements in a function provided only one of them will ever be utilized during execution of that function. For instance:
if (user === 'John') return true;
else return false;If you have faulty function structure you could end up seeing:
“unreachable code after return statement”There’s also the possibility that you might not be lucky enough to see that error message in your console if your function design is bad enough.
Conclusions
After rereading the opening paragraph to this story, I realize that I didn’t thoroughly follow the problem statement. It said to remove unique elements. That’s probably why the return variable in the original empty CheckiO function was the same as the input parameter, data. So, while I technically solved the problem, I didn’t exactly solve it. I didn’t modify an array, I created a new array.
I’m sure future challenges will be similar to this one in that regard, and I plan to be more mindful of the parameters of each one and adhere to them more stringently.
I also just updated the code on GitHub to fix the final assert.deepEqual() check that I added to see if this worked for an array that contained both ints and strings. Thank God for loosely-typed languages.
I’m always looking for feedback on how I can optimize both my algorithms and my professional writing.
