Today I was presented to this problem. Basically given a list of elements, I’d have to find the nearest distance between two elements of that list.
You can see an example of given list. Notice that we’re not talking about a set, which means that elements could possibly repeat.
Let’s go through some possible situations and answers for these situations.
Ok so let’s go to the algorithm. First of all we’re going to create a class wrapper to contain our information. We can call it
NearestIndexFinder. The initializer of this class will receive the array of elements. Here’s where our algorithm will start working. But before let’s think a little about the problem.
The computation time for this algorithm, if we have only an array to deal with, this computation time will be of an average of o(n²), because we’ll have to compare all the elements of the array with each other and pick the shortest distance. We may also have cases where the distance would be 0 in the first iteration of our loops. So then, for this specific case, we could just return 0 and the computation time will be o(1). It's possible because 0 is the shortest absolute distance between two objects. In this case, the objects are the same. But this case isn’t supposed to happen all the time and we can’t rely on it.
My first idea to solve this problem in the fastest way possible – and with no much hurt to the memory - would be to create a “cache” dictionary, where the keys are going to be the array elements, and the value of this dictionary will be the index of those elements on the original array. Our init will take a o(n) time to be initialized, but after that we can have results for our algorithm in a o(1) basis. First, let’s how could we implement the init.
Good. Now we have the cache/dictionary of elements. This dictionary will looks a little like this:
The next step would be to create a function to check the distance, which is the heart of our application/implementation. This function will return an int representing the shortest distance between two elements, or -1 if there's no possibility of calculating this distance.
First we have to check some edge cases for this function. The one I have on top of my mind now would be to see if the given strings are in that array. If that string isn’t there, we can just return -1, meaning that the distance can’t be computed. Instead of going over the array, we can just check if our dictionary contains a value for that given string. If not, it means that the given string wasn’t in the original list. This operation is executed in o(1). That’s great.
Another way to do it would be just getting those dictionaries of indexes and assigning them to a
let using a
guard let, as can be seen below:
DistancesFirst is the list of distances of the first string of this method. The explanation is analogue to the second variable.
Now there’s not much secret, we must compare the distances between all the elements of the arrays.
Basically the distance will be the absolute value of a subtraction between the first index and the second. We found it. But what can we do with this information? Maybe put those distances in a array? Let’s say a
let distances: [Int] = ? Sounds fair, but at the end we’d have to compare which is the lowest number of that list. Which means something like o(n)? We don’t want that. We can though just store the lowest number, after all, is the only thing we’re interest in, right? So let’s do that.
I made a few changes here. I created a
shortest variable. It will have initial value -1, and will be replaced as soon as we find a number or when that new number is lower than the current one stored in
shortest. Also, I moved the declaration of
let distance to outside the loop and renamed it to
distanceAux. So then we don’t instantiate this guy every time, instead will just reuse it.
We have pretty much everything. At the end of the loop we’ll have the shortest distance between the indexes of two given strings. Maybe we could just return immediately if the shortest becomes 0. After all, 0 is the shortest possible distance, meaning that those strings are the same, as discussed before. Obviously we could also only check before the for loop if the strings are equal. If yes we just return 0. Let’s keep the last option, because our if statement will be executed only once.
I guess that’s it. In a good case scenario our algorithm will be executed on o(1), worst case scenario, where most part of the strings of the list are repeated, our algorithm will be executed on something closer to o(n).
If you want to see this code running, check out my GitHub. If you liked, leave a comment and share with your network.