Online Majority Element In Subarray Solution in C++

Problem Description

Welcome to the world of online majority elements, where you can feel like a detective trying to find the most popular item in a room full of people! Imagine you’re at a party, and you want to know which snack is the favorite among your friends. But wait! You can only ask a few people at a time, and you need to make sure that the snack you choose is liked by a certain number of them. Sounds like a fun game, right?

In the LeetCode problem “Online Majority Element In Subarray,” you’re given an array of integers and need to answer queries about the majority element in a specific subarray. The catch? You have to determine if a number appears more than a given threshold in that subarray. So, if you thought finding the most popular snack was hard, try doing it with a bunch of numbers!

Code Solution


class MajorityChecker {
 public:
  MajorityChecker(vector& arr) : arr(arr) {
    for (int i = 0; i < arr.size(); ++i)
      numToIndices[arr[i]].push_back(i);
  }

  int query(int left, int right, int threshold) {
    for (int i = 0; i < kTimes; ++i) {
      const int randIndex = rand() % (right - left + 1) + left;
      const int num = arr[randIndex];
      const vector& indices = numToIndices[num];
      const auto lit = ranges::lower_bound(indices, left);
      const auto rit = ranges::upper_bound(indices, right);
      if (rit - lit >= threshold)
        return num;
    }
    return -1;
  }

 private:
  const vector arr;
  static constexpr int kTimes = 20;  // 2^kTimes >> |arr| = n
  unordered_map> numToIndices;
};

Approach Explanation

The code uses a clever approach to tackle the problem. It first stores the indices of each number in the array using a hash map. When a query is made, it randomly selects an index within the specified range and checks if that number appears frequently enough to be considered the majority. This random sampling method allows for efficient querying without needing to scan the entire subarray every time.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(k), where k is a constant (20 in this case)
Space Complexity	O(n), where n is the number of elements in the input array

Real-World Example

Imagine you’re at a concert, and you want to know which song is the crowd’s favorite. You can’t ask everyone, so you randomly pick a few people in the crowd and ask them. If enough of them say “Song A,” you declare it the crowd’s favorite for that moment. This is similar to how the algorithm works—sampling a few indices to determine the majority element in a subarray.