Thinking about coding challenges

Coding challenges can sometimes be hard. Not necessarily because the problem itself is complicated, but because you have a weird feeling and you don’t know where to approach the problem from. When you’re dealing with such problems in interviews it becomes even more cumbersome.

As such I decided to dedicate a week to writing articles regarding code challenges, so each and every day (for a week) I will randomly choose an at-least-medium difficulty problem (as graded by the platform) and I’ll go through my own thought process when solving it.

Random problem of the day: Group Anagrams

(I suggest you try it yourselves before continuing reading. You can find it here. Leetcode lists it as a problem of medium complexity)

Description: Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example: Input: strs = [ “eat”, ”tea”, ”tan”, ”ate”, ”nat”, ”bat” ]
Output: [ [ “bat” ], [ “nat”, ”tan” ], [ “ate”, ”eat”, ”tea” ] ]

The problem specifies that the result can hold the arrays in any order and that each array of anagrams can hold the words in any order.

How can we conclude if a word is an anagram of another word?

The property that makes a word an anagram of another word is that all the letters of the first word (and only those letters!) are present in the second word. Regardless of how those letters appear in the two words, we know that if we arrange them in alphabetical order, the resulting strings should be identical. In order to be able to compare the letters in the two words we will:

1. Create an array of the letters
2. Sort the array in alphabetical order (or in whatever order we want — the only thing that matters is to order them the same in each and every word)
3. Create a string from that array so that we can compare the strings themselves.

const strs = ['ate', 'tea']
// 'ate' => ['a', 't', 'e'] => ['a', 'e', 't'] => 'aet'
const firstWord = [...strs[0]].sort().join('')
// 'tea' => ['t', 'e', 'a'] => ['a', 'e', 't'] => 'aet'
const secondWord = [...strs[1]].sort().join('')

// This will return true
if (firstWord == secondWord) return true

Now we have the means to check if two words are anagrams of each other.

Grouping related anagrams in the same array

I suspect that’s the less obvious part of the problem. In order to group objects into the same category, they need to have a common property. In our case, all the anagrams, when exposed to the above operations, will result in the same string. Let’s use that to our advantage!

There are multiple approaches to keeping track of the anagrams, but the simplest that comes to my mind is having a result object that will have the resulting strings as keys and each of those keys will hold an array containing all the words that result in the same key string. Something like this:

const result = { 'aet': ['ate', 'tea'] }

Of course, we will start with an empty result object and we will add keys along the way. We will iterate over all the strings that are given to us and each time we will apply the operations meant to transform the string to its letter-ordered form. If the resulting string is already a key in the result object, we will add the string we’re iterating upon to the array held by that key. If the letter-ordered form key does not exist, we know that’s the first word of that form, we add the key, define its value as an empty array, and then push the word into that array. We’ll end up with something like this:

// Initialize the empty result object
const result = {}

// Iterate over all the strings in the input (here called strs)
for (let str of strs) {
  // Order the letters of the word in alphabetical order and obtain a string
  const letters = [...str].sort().join('')
  
  // If the string-key does not exist in the object, create it
  if (!result[letters])
    result[letters] = []
  
  // Regardless of if the string-key existed or not, push the word inside
  // the array corresponding to the string-key
  result[letters].push(str)
}

// We are only interested in the arrays held by the keys, not in the
// object itself, so we use Object.values(object) to retrieve those.
// Object.values(object) returns an array of the corresponding values
return Object.values(result)

And that’s it! Whenever you’re dealing with a problem that seems complicated try to break it down into bite-sized fragments that you’re able to comprehend and implement. I will see you tomorrow with the next random problem!