Mastering Unique Elements and Anagram Detection with Scala HashSet

Welcome to our focused exploration of Scala's HashSet and its remarkable applications in solving algorithmic challenges. In this lesson, "Mastering Unique Elements and Anagram Detection with Scala HashSet," we'll delve into how this efficient data structure can be leveraged to address and solve various types of problems commonly encountered in technical interviews.

Picture this: you're given a vast list of words, and you must identify the final word that stands proudly solitary — the last word that is not repeated. Imagine sorting through a database of unique identifiers and finding one identifier towards the end of the list that is unlike any other.

The straightforward approach is to examine each word in reverse, comparing it to every other word for uniqueness. This brute-force method results in poor time complexity, O(n^2), which is less than ideal for large datasets.

Here is the naive approach in Scala:

def findLastUniqueWordNaive(words: Array[String]): Option[String] = {
  for (i <- words.indices.reverse) {
    var count = 0
    for (j <- words.indices) {
      if (words(i) == words(j)) {
        count += 1
      }
    }
    if (count == 1) {
      return Some(words(i))
    }
  }
  None // In case no unique word is found
}

We can utilize two HashSet[String] instances: wordsSet to maintain unique words and duplicatesSet to keep track of duplicate words. By the end, we can remove all duplicated words from wordsSet to achieve our goal.

Here is how to use Scala's HashSet to solve the problem:

Create a HashSet instance to store unique words and initialize another to monitor duplicates:

import scala.collection.mutable.HashSet

val wordsSet = HashSet[String]()
val duplicatesSet = HashSet[String]()

Iterate through the word array, filling wordsSet and duplicatesSet:

for (word <- words) {
  if (wordsSet.contains(word)) {
    duplicatesSet.add(word)
  } else {
    wordsSet.add(word)
  }
}

Use the diff method from Scala's Set API to remove all duplicated words from wordsSet:

wordsSet --= duplicatesSet

Now, wordsSet only contains unique words. Find the last unique word by iterating through the original word list from the end:

var lastUniqueWord: Option[String] = None
for (i <- words.indices.reverse if lastUniqueWord.isEmpty) {
  if (wordsSet.contains(words(i))) {
    lastUniqueWord = Some(words(i))
  }
}

And finally, return the last unique word:

def findLastUniqueWordEfficient(words: Array[String]): Option[String] = {
  val wordsSet = HashSet[String]()
  val duplicatesSet = HashSet[String]()

  for (word <- words) {
    if (wordsSet.contains(word)) {
      duplicatesSet.add(word)
    } else {
      wordsSet.add(word)
    }
  }

  wordsSet --= duplicatesSet

  for (i <- words.indices.reverse) {
    if (wordsSet.contains(words(i))) {
      return Some(words(i))
    }
  }

  None
}

This efficient approach, with a time complexity close to O(n), is far superior to the naive method and showcases your proficiency in solving algorithmic problems with Scala's HashSet.