SETS

Taken from my Risk Video

This past month, I’ve been prioritizing Data Structure and Algorithms. Thankfully, when it comes to frontend development, I’ve been practicing on my mentors’ company website. Today I was doing a leetcode problem to prepare me for some job interviews and I’ve been getting better at them, thankfully, but I always forget to use Sets! This particular question, I used a hash table but then realized that I’d probably be best using a set, so let’s dive into it.

Leetcode 1436: Destination City

The Problem: You are given an array ‘paths’, where paths[i] = [‘cityA’, cityB] which means that there exists a path outgoing cityA to cityB. Return the destination city without any path outgoing to another city.

Example:

Input: [[London, New York], [New York, Lima], [Lima, Sao Paulo]]

Output: Sao Paulo because Sao Paulo doesn’t serve as the starter for another path to a city.

My thought process for this is to make a hash table where each key is the starting city, and the value is the destination city.

store = {
   London: New York,
   New York: Lima, 
   Lima: Sao Paulo
}
   

Once we have this, we can iterate through this store to find at what point does a value not equal a key which works. The issue with this solution is that it takes a while to code out. Like most people, I’m a fan of easy to read, clear and DRY code. First thing I had to do for this was iterate through the matrix and create the key value pairs for the store as seen below.

for(let i = 0; i < paths.length; i++){
   let cityA = paths[i][0]
   let cityB = paths[i][1]
   if(!store[cityA]){
      store[cityA] = cityB
   }else{
      return cityB
   }
}

Now that that’s been created, I iterate through the store and find if there is a value to any key that does not exist as a key itself.

for(let start in store){
   let value = store[start]
   if(!store[value])return value
}

This works, but I know that there’s an easier way to do this. The reason I opt to go for hash tables is because it’s honestly just what I’m use to. If you think about it, I’m looking to compare all the existing value pairs, with all the existing keys and if the value does not exist as a key, then we know which city we’d like to return! When it comes to unique values, think about Sets. All values inside the set are unique which means, they don’t repeat so let’s use it.

PseudoCode

• Let’s create a set from all the outgoing cities, or cityA.
• Let’s check to see if the set contains all destination points, or cityB.
• If there exists a cityB that is not included in the set, return it

const set = new Set();
for (let path of paths) set.add(path[0])
for (let path of paths){
   if(set.has(path[1]))return path[1]
}

This looks so much better and much more readable than what I previously had. Again, when you find yourself having to store unique elements, use Sets not hash tables! Lastly, I know I don’t return anything if I don’t find a city but I’ll leave that up to you. You can return undefined or whatever you’d like!

That’s all for this weeks blogs. I’m glad I came across this leetcode problem because I often stick to three or four data structures without making complete use of the rest. It’s a reminder to get comfortable using all of them.

As always, happy coding!