Efficient Problem Solving with Scala Maps: Majority Element and Keyword Index Creation

Welcome back! Today, we're sharpening our algorithmic problem-solving skills, focusing on Map in Scala. Imagine Map as the backbone of a social network app, ensuring that each user's data remains unique and instantly accessible. By the close of this lesson, you will be equipped to use Scala's Map to efficiently solve problems that might otherwise seem daunting due to their complexity or data size.

Our journey begins with the Majority Element Finder. You're handed an array of integers, and your mission is simple yet intriguing: determine whether this array has a celebrity element. This integer appears more frequently than all others combined. More formally, we are looking for an element appearing more than n/2 times.

Why does this matter? Well, consider analyzing sales data to determine the most sold product in an online marketplace — knowing the majority of products could streamline marketing strategies and inventory management. That's the real-world relevance of the majority element problem.

Let's delve into how Scala's Map can serve as our efficient tally system.

Let's dissect the process in an election analogy step by step:

var countMap = scala.collection.mutable.Map[Int, Int]()
val majorityThreshold = arr.length / 2

Here, we're preparing our Map, akin to setting up our ballot boxes and establishing the majority threshold — the number of votes needed to win the election by a landslide.

for (num <- arr) {
  val count = countMap.getOrElse(num, 0) + 1
  countMap(num) = count

We're recording every vote cast in our Map ledger. Each key is a unique product, and the value is the current total of received votes.

  if (count > majorityThreshold) {
    return num
  }
}

Once a product's vote count exceeds the threshold — signaling a majority — our search concludes, akin to declaring a winner!

def findMajorityElement(arr: Array[Int]): Int = {
  val countMap = scala.collection.mutable.Map[Int, Int]()
  val majorityThreshold = arr.length / 2

  for (num <- arr) {
    val count = countMap.getOrElse(num, 0) + 1
    countMap(num) = count 

    if (count > majorityThreshold) {
      return num
    }
  }

  -1
}

If the polling ends with no majority victor, we return -1, signifying a contested market where no single product dominates.