Group Anagrams

Last modified date

Comments: 0

The group anagrams problem is a common interview question and is quite tricky to solve on the face of it. But there are some useful functions that are used in this answer to help you solve the problem with minimal code and an efficient runtime.

Problem

Given an array of strings, group anagrams together.

Test Cases

InputOutput
["eat", "tea", "tan", "ate", "nat", "bat"][ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]

Solution

The solution to this problem works by sorting the characters in each word into alphabetical order, and then using that as a key in a Map. Since all anagrams will have the same sorted character array, we can build up the list of anagrams in the Map.

The computeIfAbsent() function is useful in providing a clean solution for finding existing keys and adding the anagram to the list, or creating a new list in the Map.

Runtime Complexity

The outer for loop is O(n) complexity, where n = the length of the array.

The sort operation on the character array, assuming the Java implementation of sort uses the most efficient complexity, has the runtime of O(k log(k)).

Therefore the runtime complexity of O(n klog(k)).

Space Complexity

We are creating a new map that holds all n elements of the array, so O(n).

For each word we create a local variable of size O(k), the size of the word.

Therefore the space complexity is O(nk).

JakTech

Leave a Reply

Your email address will not be published. Required fields are marked *

Post comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.